Day 42 || 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ、70. 爬楼梯（进阶）

完全背包

题目链接：卡码网第52题

思路：和之前01背包一样，但是物品可以无限放置，所以之前二维数组中的背包容量是倒序遍历的，现在可以正序遍历即可重复放入。

import java.util.Scanner;
public class Main {
    public static void main (String[] args) {
        Scanner scaner = new Scanner(System.in);
        int kind = scaner.nextInt();
        int size = scaner.nextInt();
        int[] weight = new int[kind];
        int[] value = new int[kind];
        for (int i=0;i<kind;i++){
            weight[i]=scaner.nextInt();
            value[i]=scaner.nextInt();
        }
        int[][] dp = new int[kind+1][size+1];
        for(int i=1;i<=kind;i++){
            for (int j=0;j<=size;j++){
                if(j>=weight[i-1]){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
                }else {
                    dp[i][j] = dp[i - 1][j]; // 如果不能放入第 i 件物品
                }        
            }
        }
        System.out.println(dp[kind][size]);
    }
}

518. 零钱兑换 II

题目链接：力扣题目链接

思路：因为是可以无限使用相同规格的金币，完全背包和之前一样容量正序即可；但是需要注意的是因为是求可能性的数量所以需要初始化容量为0时候为1。

//一维
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // 初始状态，凑成金额0的组合数为1（即什么都不选）

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}

//二维
class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];
       
        // 初始化：凑成金额0的方法只有1种，即不选任何硬币
        for (int j = 0; j <= coins.length; j++) {
            dp[j][0] = 1;
        }
        
        // 填充 dp 表
        for (int j = 1; j <= coins.length; j++) {
            for (int i = 0; i <= amount; i++) {
                if (i >= coins[j - 1]) {
                    // 使用当前硬币或不使用当前硬币的组合数
                    dp[j][i] = dp[j - 1][i] + dp[j][i - coins[j - 1]];
                } else {
                    // 无法使用当前硬币，只能继承上一个状态的组合数
                    dp[j][i] = dp[j - 1][i];
                }
            }
        }
        
        return dp[coins.length][amount];
    }
}