网站制作费用网页设计与制作书籍
LeetCode:518. 零钱兑换 II
518. 零钱兑换 II - 力扣（LeetCode）
1.思路
求组合数，先遍历物品再遍历背包，dp[]数组累加即可。
2.代码实现
1class Solution {2 public int change(int amount, int[] coins) {34 int[] dp = new int[amount + 1];5 dp[0] = 1;67 for (int i = 0; i < coins.length; i++) {8 for (int j = coins[i]; j <= amount; j++) {9 dp[j] += dp[j - coins[i]];
10 }
11 }
12 return dp[amount];
13 }
14}
3.复杂度分析
时间复杂度：O(nm). 空间复杂度：O(nm).
LeetCode:377. 组合总和 Ⅳ
377. 组合总和 Ⅳ - 力扣（LeetCode）
1.思路
声明初始化dp数组，求排列，先遍历背包后遍历物品。dp[]数组累加操作。
2.代码实现
1class Solution {2 public int combinationSum4(int[] nums, int target) {3 int[] dp = new int[target + 1];4 dp[0] = 1;56 for (int i = 0; i <= target; i++) {7 for (int j = 0; j < nums.length; j++) {8 if (i >= nums[j]) {9 dp[i] += dp[i - nums[j]];
10 }
11 }
12 }
13 return dp[target];
14 }
15}
3.复杂度分析
时间复杂度：O(nm). 空间复杂度：O(nm).