【算法刷题day44】Leetcode：518. 零钱兑换 II、377. 组合总和 Ⅳ

草稿图网站
java的Deque

Leetcode 518. 零钱兑换 II

题目：518. 零钱兑换 II
解析：代码随想录解析

解题思路

先遍历物品，再遍历背包。

代码

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

总结

暂无

Leetcode 377. 组合总和 Ⅳ

题目：377. 组合总和 Ⅳ
解析：代码随想录解析

解题思路

先遍历背包，再遍历物品

代码

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

总结

暂无