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

完全背包理论

直接的说明就是把01背包的有限次选取变为无限次选取求最大价值

相对的 遍历方向也可以相互调换 因为dp[j]只需要上次的计算结果就行 

public class CarlcodeAllBag {
    public static void testCompletePack(){
        //先遍历物品 再遍历背包
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;
        int[] dp = new int[bagsize + 1];
        for(int i = 0; i < weight.length; i++){
            //遍历物品
            for(int j = weight[i]; j <= bagsize; j++){//遍历背包
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        for(int maxvalue : dp){
            System.out.println(maxvalue + " ");
        }
    }
}

518. 零钱兑换 II

题目链接：518. 零钱兑换 II - 力扣（LeetCode）

讲解链接：代码随想录

对上一次写的求目标和里的递推公式看不明白 导致我现在跟不上代码 得返工 讨厌返工

Java代码：

class Solution{
    public int change(int amount, int[] coins){
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组 表示金额为0 时只有一种情况 什么都不装
        dp[0] = 1;
        for(int i = 0; i < coins.length; i++){
            for(int j = coins[i]; j <= amount; j++){
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

 377. 组合总和 Ⅳ

题目链接：377. 组合总和 Ⅳ - 力扣（LeetCode）

讲解链接：代码随想录

还是那个公式  现在看懂了 重新看了一遍 就是填满容积i一般大的背包需要dp[i]种可能的方案

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. 爬楼梯 （进阶）

题目链接：代码随想录

讲解链接：代码随想录

 完全背包求排列问题 一旦扩展到m或n就可以用这个方法 比较泛用

先遍历背包再遍历物品 自己琢磨了一下 看了ai给我的解答看懂了

class Solution{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m, n;
        while(sc.hasNextInt()){
            //从键盘输入参数 中间用空格隔开
            n = sc.nextInt();
            m = sc.nextInt();
            //求排列问题 先遍历背包再遍历物品
            int[] dp = new int[n + 1];
            dp[0] = 1;//初始化
            for(int j = 1; j <= n; j++){
                for(int i = 1; i <= m; i++){
                    if(j - i >= 0) dp[j] += dp[j - i];
                }
            }
            System.out.println(dp[n]);
        }
    }
}

打卡