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]);}}
}