算法训练营day38 | {0.完全背包（纯）, 518.零钱兑换 II, 377.组合总和 Ⅳ, 70. 爬楼梯 （进阶）}

第九章动态规划part05，完全背包应用，注意组合数、排列数在遍历顺序上的区别。

0. 完全背包（纯）

0.1 理论基础

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。对于不考虑应用场景的纯粹01背包问题，先遍历物品或是先遍历背包都是可以的。

0.2 完全背包-二维数组

举个例子学习完全背包的DP五部曲（二维dp），例如背包最大重量为4，物品为：

重量价值
物品0115
物品1320
物品2430

每件商品都有无限个，问背包能背的物品最大价值是多少？

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i][j]的定义：从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。
  2. 确定递推公式: dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
  3. dp数组如何初始化: 从dp[i][j]的定义出发，如果背包容量j为0，dp[i][0] = 0; 取物品0时，当j < weight[0], dp[i][0] = 0, 当>= weight[0]时，就一直装，每一种物品就无限个。
  4. 确定遍历顺序: 先遍历物品还是先遍历背包都是可以的。
  5. 举例推导dp数组: 二维dp数组递推模拟

注意事项：

  • 关于递推公式：不放物品i这里和01背包有区别了，空出物品i的容量之后，背包里原来仍有可能可以放物品i。
  • 关于初始化：一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
  • 解题的时候，j的遍历起点错了，当j < weight[i]时，没有给dp[i][j]赋值，但这些状态应该继承上一行 dp[i][j] = dp[i - 1][j];
  • dp数组第一行的初始化不够通用，让递推统一处理更标准。
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
31
32
33
34
35
36
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 物品个数
        int v = scanner.nextInt();  // 背包容量
        int[] value = new int[n];
        int[] weight = new int[n];
        for (int i = 0; i < n; i++) {
             weight[i] = scanner.nextInt();
             value[i] = scanner.nextInt();
        }

        System.out.println(Main.knapsack(weight, value, n, v));
    }

    private static int knapsack(int[] weight, int[] value, int n, int v) {
        int[][] dp = new int[n][v + 1];
        for (int i = 0; i < n; i++) dp[i][0] = 0;
        for (int j = 0; j <= v; j++) {
            dp[0][j] = (j >= weight[0]) ? dp[0][j - weight[0]] + value[0] : 0;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= v; j++) {
                if (j >= weight[i])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n - 1][v];
    }
}

0.3 完全背包-一维数组

将二维DP数组，压缩成一维DP数组，也就是将上一层拷贝到当前层。递推公式变为：

  • dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    其实不管是dp数组定义、还是遍历顺序，在想的时候就和二维dp数组一样想，所以无所谓先遍历物品还是背包容量。
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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 物品个数
        int v = scanner.nextInt();  // 背包容量
        int[] value = new int[n];
        int[] weight = new int[n];
        for (int i = 0; i < n; i++) {
             weight[i] = scanner.nextInt();
             value[i] = scanner.nextInt();
        }

        System.out.println(Main.knapsack(weight, value, n, v));
    }

    private static int knapsack(int[] weight, int[] value, int n, int v) {
        int[] dp = new int[v + 1];

        for (int i = 0; i < n; i++) {
            for (int j = weight[i]; j <= v; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        return dp[v];
    }
}

518. 零钱兑换 II

1.1 解题分析

硬币的价值就是硬币的重量，题目要求背包容量为amount，把背包装满有几种方案？不考虑硬币放入背包的顺序。每一种面值的硬币有无限个，典型的完全背包问题，dp数组的定义是关于方案个数的。

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i][j]的定义：从下标为[0~i]的硬币中任取无限次，容量为j的背包有dp[i][j]种装满的方式。
  2. 确定递推公式: dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]
  3. dp数组如何初始化:
    • 第一列dp[i][0]: 当背包容量为0时，因为硬币coin[i]面值不可能为0，只有一种组合方案，就是不装，所以dp[i][0] = 1
    • 第一行dp[0][j]: 当放硬币coin[0]时，如果 j能被coin[0]整除，那有1种方案，否则没有。
  4. 确定遍历顺序: 求组合数应该先遍历物品再正序遍历背包。
  5. 举例推导dp数组:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];
        for (int i = 0; i < n; i++) dp[i][0] = 1;
        for (int j = 0; j <= amount; j++) {
            dp[0][j] = (j % coins[0] == 0) ? 1 : 0;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j >= coins[i])
                    dp[i][j] = dp[i - 1][j] + dp[i][j -coins[i]];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n - 1][amount];
    }
}

压缩物品的维度，考虑一维dp数组。

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[j]的定义：从下标为[0~i]的硬币中任取无限次，容量为j的背包有dp[j]种装满的方式。
  2. 确定递推公式: dp[j] = dp[j] + dp[j - coins[i]]
  3. dp数组如何初始化:
    • 背包容量为0时，有1种方法装满，就是不装，dp[0] = 1
    • 其他位置，因为要累加所以全部初始化为0
  4. 确定遍历顺序: 求组合数应该先遍历物品再正序遍历背包。
  5. 举例推导dp数组:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        int n = coins.length;
        dp[0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

377. 组合总和 Ⅳ

2.1 解题分析

DP五部曲：

  1. dp[j]数组定义：顺序不同，算不同方案，dp的语义必须是凑成j的排列数有dp[j]种
  2. 递推公式：
    • 也就是说最后一个数是谁，是重要信息，假设最后一个数是num
    • dp[j] += dp[j - num]
  3. dp数组初始化：
    • dp[0] = 1
  4. 遍历顺序：因为是求排列数，先遍历背包，再遍历物品
  5. 打印dp数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 1; j <= target; j++) {
            for (int num : nums) {
                if (j - num >= 0)
                    dp[j] += dp[j - num];
            }
        }
        return dp[target];
    }
}

70. 爬楼梯 （进阶）

2.1 解题分析

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

你有一个背包容量为n，有物品重量从1到m，无限个，请问凑到容量n的排列数是几种？问题转化为完全背包的排列数。同样的，在维度1不能锁定物品出现的顺序，否则就是在算组合数。

DP五部曲：

  1. dp[j]数组定义：顺序不同，算不同方案，dp的语义必须是凑成j的排列数有dp[j]种
  2. 递推公式：
    • 也就是说最后一个数是谁，是重要信息，假设最后一个数是num
    • dp[j] += dp[j - num]
  3. dp数组初始化：
    • dp[0] = 1
  4. 遍历顺序：因为是求排列数，先遍历背包，再遍历物品
  5. 打印dp数组。

2.2 解题小结

和377. 组合总和 Ⅳ是一模一样的。

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] nums = new int[m];
        for (int i = 0; i < m; i++) {
            nums[i] = i + 1;
        }
        
        System.out.println(Main.knapsack(nums, n));
    }

    private static int knapsack(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 1; j<= target; j++) {
            for (int num : nums) {
                if (j - num >= 0) dp[j] += dp[j - num];
            }
        }
        return dp[target];
    }
}

Leetcode > 动态规划
#Java #代码随想录
算法训练营day38 | {0.完全背包（纯）, 518.零钱兑换 II, 377.组合总和 Ⅳ, 70. 爬楼梯 （进阶）}
http://paopaotangzu.xyz/cn/day38_leetcode/
作者
PROTON TANG
发布于
2026年1月26日
许可协议