算法专题：完全背包、零钱兑换及爬楼梯问题解析

完全背包问题

题目描述

给定物品重量和价值，求在背包容量限制下的最大价值。

核心思路

1. 确定 dp 数组及其下标含义 定义一维 dp 数组，下标表示背包大小。

2. 确定递推公式 因为完全背包的物品是无限个，所以放完了一个，还能在同一层找。 二维递推公式写法：dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]) 一维递推公式写法：dp[j] = max(dp[j], dp[j - w[i]] + v[i])

3. 初始化数组 全部为 0。

4. 确定循环顺序 因为完全背包物品有无限个，所以遍历背包可以正序遍历，这样正好默认是在同一层。

易错点

一维递推公式写法：dp[j] = max(dp[j], dp[j - w[i]] + v[i])

零钱兑换 II

题目描述

计算凑成总金额的组合数。

核心思路

1. 定义一维 dp 数组 dp[j] 为填满背包大小为 j 的背包的组合数有 dp[j] 种。

2. 确定递推公式 因为求的是方法有多少种，所以用累加的形式： dp[j] = dp[j] + dp[j - w[i]]; 表示填满当前背包有两种来源： 不放物品 i，那么就是 dp[j]。 放物品 i，那么就是 dp[j - w[i]]。

3. 初始化 dp 数组 dp[0] = 1;

4. 确定遍历方向 先遍历物品，再遍历背包。背包是正序遍历。

易错点

1. 背包大小要从 w[i] 开始，放不进就默认 dp[j]。
2. dp 数组的类型为 unsigned long long。

组合总和 IV

题目描述

计算凑成目标值的排列数。

核心思路

1. 定义一个一维 dp 数组 dp[j] 表示当背包为 j 时，排列数为多少个。

2. 确定递推公式 dp[j] = dp[j] + dp[j - w[i]];

3. 初始化 dp 数组 dp[0] = 1;

4. 确定遍历顺序 因为求的是排列数，对顺序有要求，那我们就考虑填满每个背包大小的最后一个值是什么。因为每个背包大小都要考虑，所以物品在内层循环。

易错点

1. dp 数组的类型为 unsigned long long。
2. 遍历顺序为，背包在外，物品在内。

爬楼梯

题目描述

每次可以爬 1 到 m 个台阶，求爬到第 n 阶的方法数。

核心思路

1. 确定一维 dp 数组及其下标含义 dp[j] 表示爬上台阶为 j 总共有 dp[j] 种方法。

2. 推导递推公式 dp[j] = dp[j] + dp[j - w[i]];

3. 初始化数组 dp[0] = 1;

4. 确定遍历顺序 因为是排列数，所以物品放内，背包放外。

易错点

1. 台阶个数是背包大小，一次可以爬多少个台阶是物品。
2. 初始化了台阶个数为 0 时的方法，所以背包从 1 开始。
3. 物品从 1 开始，小于等于 m。