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

完全背包问题

        和01背包最大区别就是一个物品可以重复放多次，因此遍历空间时可以从前往后。

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] weight = new int[m];
        int[] value = new int[m];
        for(int i = 0; i < m; i++){
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int[] dp = new int[n+1];
        
        for(int i = 0; i< weight.length; i++){
            for(int j = weight[i]; j<=n; j++){
                if(j-weight[i] >=0){
                    dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);

                }
            }
        }
        
        System.out.println(dp[n]);
        
        

    }
}

518.零钱兑换II

        这题一定要手推以下dp数组才能更好理解，虽然费电时间，但感觉一点点疏通了。

        dp[j] :装满j的背包，要多少种方法。

        递推公式：                dp[j] += dp[j-coins[i]];

        凡是装满容量为[j]的背包有多少种方法，都是这个公式。

        初始化：dp[0] = 1；设置为0的话地推出来都是0        

        遍历顺序：外层遍历物品，内层遍历背包，遍历出来是组合数。

如果反过来，外层遍历背包，内层遍历物品，遍历出来是排列数。

        打印dp数组：手推的时候，我把这题类比成爬楼梯，外层遍历的是腿长，代表我一次能跨几个台阶，内层遍历的就是台阶高度了。一开始腿长只是1，到达任意台阶都只能一步一步上去，所以就是dp[j] = 1；然后能跨两步的时候，是把一步一步跨的dp[j]，加上当前台阶减去两步的最大方法数（dp[j-2]），加起来。这里计算的是方法数，不是步数，所以不需要再加1.因为在j-2的台阶往j台阶。要么一步一步跨(dp[j] 就是这种情况)，要么跨两步（就是dp[j-2]）。

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. 组合总和 Ⅳ

        如果上题手推，这题就是小葱拌豆腐，不再分析了。

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 i = 0; i< nums.length; i++){
                if(j-nums[i] >= 0){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }

        return dp[target];
    }
}

70. 爬楼梯（进阶版）

        在写零钱兑换题解的时候还没写这题，自己进行了类比，没想到这就来了。基本就是照抄了。

import java.util.*;

public class Main{
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int 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){
                    dp[j] += dp[j - i];
                }
                
            }
        }
        System.out.println(dp[n]);
    }
}