518.零钱兑换II
文章讲解/视频讲解
题目描述：
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
- 输入: amount = 5, coins = [1, 2, 5]
- 输出: 4
解释: 有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
示例 2:
- 输入: amount = 3, coins = [2]
- 输出: 0
- 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
- 输入: amount = 10, coins = [10]
- 输出: 1
注意，你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
思路：
本题就很像之前做过的“目标和”，都是给出背包容量，求装满背包的方法数。但是“目标和”每个元素只能使用一次，前面我们介绍过了这是01背包的特征。而本题每种面额的硬币都有无穷个，所以这就是之前提到过的完全背包，一样来写动态规划五部曲
1.确定dp数组及其下标含义：dp[i][j]：使用 下标为[0, i]的coins[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种组合方法。
2.确定递推公式：完全背包递推公式与01背包的区别在于：
01背包递推公式为:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，01背包如果放了物品i，再取就只能拿物品0到物品i - 1这个范围了，物品i拿不了。
而完全背包公式为：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])，因为有无限个物品，我拿完物品i下一次还是能从物品0到物品i的区间里拿。
本题的一维dp数组递推公式为dp[j] += dp[j - coins[i]]，与目标和一致，之前讲过这里不再过多赘述
3.dp数组的初始化：我们要关注的就是dp[0]，装满背包容量为0的方法是1，即不放任何物品，dp[0] = 1
4.确定遍历顺序：完全背包的两个for循环随便先后顺序都可以，但是本题不行！因为本题本质和元素凑成的顺序没多大关系，本题描述也是求组合数。假设存在结果221和212，如果求的组合数，那就只有一种，如果是求排列数那么这可就算两种排列了。
我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。
代码如下：
for (int i = 0; i < coins.size(); i++) { // 遍历物品 for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量 dp[j] += dp[j - coins[i]]; } }假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：
for (int j = 0; j <= amount; j++) { // 遍历背包容量 for (int i = 0; i < coins.size(); i++) { // 遍历物品 if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]]; } }背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
所以一定是先遍历物品，再遍历背包容量，想不明白就打印数组自己看看
5.举例推导dp数组
输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：
最后红色框dp[amount]为最终结果。
代码示例：
function change(amount: number, coins: number[]): number { const dp:number[] = new Array(amount + 1).fill(0) dp[0] = 1 for(let i = 0 ; i < coins.length; i++){ for(let j = coins[i]; j <= amount; j++){ dp[j] += dp[j - coins[i]] } } return dp[amount] };377.组合总和IV
文章讲解/视频讲解
题目描述：
难度：中等
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
- nums = [1, 2, 3]
- target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
思路：
与上题一样的思路，但是换成了求排列，虽然本题题干说的是求组合，但是我们对组合的定义其实是不强调顺序，即1,5和5,1算同一个组合，但其实算两个不同的排列。
1.确定dp数组及其下标含义：dp[i]：凑成目标正整数为i的排列个数为dp[i]
2.确定递推公式：之前说过了，只要是求装满背包有几种方法，一般都是用：dp[i] += dp[i - nums[j]
3.dp数组如何初始化：dp[0]一定要初始化为1，否则递归其他dp[i]就没有数值基础了，其他全部初始化为0，避免影响dp[i]累加
4.确定遍历顺序：上一题求的是组合，我们先遍历物品再遍历背包，本题求的是排列，所以是先遍历背包再遍历物品。
5.举例来推导dp数组
我们再来用示例中的例子推导一下：
代码示例：
function combinationSum4(nums: number[], target: number): number { const dp:number[] = new Array(target + 1).fill(0) dp[0] = 1 for(let i = 1; i <= target; i++){ for(let j = 0; j < nums.length; j++){ if(i >= nums[j]){ dp[i] += dp[i - nums[j]] } } } return dp[target] };爬楼梯（进阶）
文章讲解
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述：输入共一行，包含两个正整数，分别表示n, m
输出描述：输出一个整数，表示爬到楼顶的方法数。
输入示例：3 2
输出示例：3
提示：
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶段
- 1 阶 + 2 阶
- 2 阶 + 1 阶
思路：
其实我们之前就写过一道爬楼梯了，力扣上那道是一次只能爬一节或两节，本题可以爬1到m任意节，其实还是一个完全背包。每次能爬的阶数就是物品，楼顶就是背包容量，我这次跳了一节，下次还能再跳一次一节，也就是物品可以重复使用。而问跳到楼顶有几种方法，其实不就是问装满背包有几种方法吗？
1.确定dp数组及其下标含义：dp[i]：爬到i个台阶的楼顶，有dp[i]种方法
2.确定递推公式：求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];本题比较特殊，dp[i]的来源是dp[i -1],dp[i -2]......，也就是dp[i - j]，所以递推公式为dp[i] += dp[i - j]
3.dp数组如何初始化：依旧是dp[0]为1，其他非零下标全是1
4.确定遍历顺序：这里先上一节再上三节，和先上三节再上一节，最后都上了四节，但是算两种不同的方法，前面提到过，这种我们称作排列，也就是背包容量在外面循环，物品在内循环。
5.举例推导dp数组：与上题基本一致
代码示例：
var climbStairs = function (n: number): number { let dp: number[] = new Array(n + 1).fill(0); dp[0] = 1; for (let j = 1; j <= n; j++) {//遍历背包 for (let i = 1; i <= 2; i++) {//遍历物品 if (j - i >= 0) dp[j] = dp[j] + dp[j - i]; } } return dp[n]; }
