代码随想录算法训练营第三十六天-完全背包、518零钱兑换 II、377组合总和 Ⅳ、CM70爬楼梯（进阶）
初步题解
518 零钱兑换 II
题目链接：(https://leetcode.cn/problems/coin-change-ii/)
-
确定 dp[i] 的含义：填满 i（包括 i）这么大容积的包，有 dp[i] 种方法
-
递推公式：dp[i] += dp[i - coin]。
-
dp 数组的初始化：dp[0] = 1。假设数组个数为 0，获取 dp[0]，就是 1。
-
遍历顺序：从前向后遍历。
-
打印 dp 数组（用于 debug）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i < dp.length; i++) {
dp[i] += dp[i - coin];
}
}
System.out.println(Arrays.toString(dp));
return dp[amount];
}
|
377 组合总和 Ⅳ
题目链接：(https://leetcode.cn/problems/combination-sum-iv)
如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。
如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public static int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < dp.length; i++) {
for (int num : nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
System.out.println(Arrays.toString(dp));
return dp[target];
}
|
70 爬楼梯 （进阶）
题目链接：(https://kamacoder.com/problempage.php?pid=1067)
就是完全背包 + 排列，解法和上题一模一样。nums 取值为 1- 每次最多爬的阶梯数量
看解析
完全背包
有 N 件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和 01 背包问题唯一不同的地方就是，每种物品有无限件。
二维数组：
-
递推公式：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - item[i][0]] + item[i][1])（即，不重复存放当前物品/重复存放当前物品）
-
dp 数组的初始化：dp[i][0] 均为 0。dp[0][j] 为第一格按背包大小取重复值。
-
遍历顺序：从前向后遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public static void main(String[] args) {
integerBreak(4, new int[][]{{1, 15}, {3, 20}, {4, 30}});
}
public static void integerBreak(int n, int[][] item) {
int[][] dp = new int[item.length][n + 1];
for (int j = 1; j < dp[0].length && n >= item[0][0]; j++) {
dp[0][j] = j / item[0][0] * item[0][1];
}
for (int i = 1; i < item.length; i++) {
for (int j = 1; j <= n; j++) {
if (j - item[i][0] < 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - item[i][0]] + item[i][1]);
}
}
}
System.out.println(Arrays.deepToString(dp));
}
|
一维数组（状态压缩）：
-
递推公式：dp[i] = Math.max(dp[i], dp[i - item[0]] + item[1]);
-
dp 数组的初始化：dp[0] = 0
-
遍历顺序：从前向后遍历。（而完全背包的物品是可以添加多次的，所以要从小到大去遍历。（😅老实说，看了好几几遍都没懂））
-
这里完全背包一维 dp 数组可以交换遍历顺序：因为 dp[j] 是用到其左边的数据 dp[j - weight[i]] 的，而先遍历背包再遍历物品也是满足的。
1
2
3
4
5
6
7
8
9
10
11
12
| public static void integerBreak1(int n, int[][] items) {
int[] dp = new int[n + 1];
for (int[] item : items) {
for (int i = 0; i < dp.length; i++) {
if (i >= item[0]) {
dp[i] = Math.max(dp[i], dp[i - item[0]] + item[1]);
}
}
}
System.out.println(Arrays.toString(dp));
}
|
518 零钱兑换 II
解析：(https://programmercarl.com/0518.零钱兑换II.html)
377 组合总和 Ⅳ
解析：(https://programmercarl.com/0377.组合总和Ⅳ.html)
70 爬楼梯 （进阶）
解析：(https://programmercarl.com/0070.爬楼梯完全背包版本.html)