leetcode 刷题day36动态规划Part05 背包问题（完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、70. 爬楼梯 （进阶））

完全背包

完全背包的每件商品都有无限个，和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次，01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的，所以要从小到大去遍历。

518. 零钱兑换 II

思路：每一种面额的硬币有无限个是完全背包问题。背包的容量为amount，物品的重量和价值都是硬笔金额。求组合数，
dp[j]表示容量为j时成立的组合数。

代码如下：

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

思路：本题与上一题的区别在于本题是求排列的个数。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

代码如下：

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

70. 爬楼梯 （进阶）

思路：dp[i]指爬到有i个台阶的楼顶，有dp[i]种方法。台阶可以重复使用-完全背包问题，从前往后遍历背包。求排列的个数，背包是外层循环。

代码如下：

import java.util.Scanner;
class Main{
    public static void main(String [] args){
        Scanner scan=new Scanner(System.in);
        int m,n;
        while (scan.hasNextInt()) {
            n=scan.nextInt();
            m=scan.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]);
        }
    }
}