518. 零钱兑换||
题目链接：力扣
思路
这道题目可以算是 纯完全背包问题 和 目标和 的结合体
总的来说就是当物品可以无限使用的时候，装满背包有多少种方法
初始化和递推公式跟 目标和 一样
遍历方式和 纯的完全背包问题 一样，但是背包的遍历和物品的遍历不能替换顺序，因为纯完全背包理论求的是填满背包的最大物品重量，而这道题目求得是有多少种方法
遍历顺序很重要：
如果求组合数，就是外层for循环遍历物品，内层for循环遍历背包
如果求排列数，就是外层for循环遍历背包，内层for循环遍历物品
零钱兑换||
class Solution { public int change(int amount, int[] coins) { // 创建dp数组 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循环遍历物品
只需要改变遍历的顺序，先对背包进行遍历，再对物品进行遍历就可以
组合总和IV
class Solution { public int combinationSum4(int[] nums, int target) { // 创建dp数组 int[] dp = new int[target + 1]; // 初始化dp数组 dp[0] = 1; // 填充dp数组 // 与组合数的遍历顺序相反,先遍历背包，再遍历物品 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]; } }
