代码随想录算法训练营 | 完全背包，518. 零钱兑换 II，377. 组合总和 Ⅳ，70. 爬楼梯 （进阶）

完全背包
题目链接：完全背包
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰完全背包
日期：2024-10-11

想法：dp数组设置思路跟01背包一样，不同在遍历上，完全背包遍历背包大小是从weight[i]开始的（背包空间小于weight[i]就没有意义，不用考虑，直接用之前的对应数值就行了），从前往后遍历就能够是重复使用物品i的效果。
Java代码如下：

import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int bagweight = scanner.nextInt();
        int[] weight = new int[N];
        int[] value = new int[N];
        for(int i = 0; i < N; i++) {
            int w = scanner.nextInt();
            int v = scanner.nextInt();
            weight[i] = w;
            value[i] = v;
        }
        int[] dp = new int[bagweight + 1];
        
        for(int i = 0; i < N; i++) {
            for(int j = weight[i]; j <= bagweight; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[bagweight]);
    }
}

518. 零钱兑换 II
题目链接：518. 零钱兑换 II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰零钱兑换 II
日期：2024-10-11

想法：求组合数的问题+完全背包，唯一难点在于初始化dp[0]，按理说dp[0]代表：有多少组合能让零钱和为0，按理应该是0，但这里要设置为1，才能保证j = amount时有个加1的效果。
Java代码如下：

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]]; 
            }
        }
        return dp[amount];
    }
}

377. 组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰组合总和 Ⅳ
日期：2024-10-11

想法：组合{1，3}{3，1}为不同组合，如果再按照上一题的思路，只能计算一次{1，3}，找不完所有组合，但遍历顺序反一下，从背包大小为0开始，在遍历nums，就会有{1，3}{3，1}这两种情况了，同时注意，此时i为背包大小，要i >= nums[j]时才放的下nums中第j个数。
Java代码如下：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if(i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

70. 爬楼梯 （进阶）
题目链接：70. 爬楼梯 （进阶）
文档讲解︰代码随想录(programmercarl.com)
日期：2024-10-11

想法：完全背包的思路解决。
Java代码如下：

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[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i = 0; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(i >= j) {
                    dp[i] += dp[i - j]; 
                }
            }
        }
        System.out.println(dp[n]);
    }
}