● 518. 零钱兑换 II
这道题考的是组合，而不是排列，关于这一点在b站的评论说的很清晰：
关于组合和排列的问题还是有些不解。以下仅为自己的理解：先遍历物品后遍历背包是这样，比如，外层循环固定coins【1】，在内层循环遍历背包时，随着背包不断增加，coins【1】可以重复被添加进来，而由于外层循环固定了，因此coins【2】只能在下一次外层循环添加进不同大小的背包中，这么看的话，coins【i+1】只能在coins【i】之后了；如果先遍历背包后遍历物品，那么外层循环先固定背包大小j，然后在大小为j的背包中循环遍历添加物品，然后在下次外层循环背包大小变为j+1，此时仍要执行内层循环遍历添加物品，也就会出现在上一轮外层循环中添加coins【2】的基础上还能再添加coins【1】的情况，那么就有了coins【1】在coins【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. 组合总和 Ⅳ
这是排列问题；
不是很清楚到底什么意思，这是我的思考过程：
现在，i就是我的目标数，我一开始担心为什么要判断当前的num【j】小于i呢，万一前面的加一块再加上nums【j】超过i咋办，这就是对dp数组理解错误了，dp数组的含义是方法数，方法数！
所以这个if的意思应该是，如果，我num【j】已经大于i了，那么这个方法直接不计入，否则，我就计入。计入的方法也有讲究，他是dp【i-nums【j】】，答案是通过正上方以及上一行左方位获得，你不一定就加上左上方的哪个方法数了，应该是这个意思吧。。。。。
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(nums[j]<=i){dp[i] += dp[i-nums[j]];} }}return dp[target];}
}●70. 爬楼梯 （进阶）
注意j的范围
import java.util.Scanner;public class Main{public static void louti(int n ,int m){int[] dp = new int[n+1];dp[0]=1;for(int i = 0;i<=n;i++){for(int j = 1;j<=m;j++){if(i>=j){dp[i]+=dp[i-j];}}}System.out.println(dp[n]);}public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();louti(n,m);}
}
