广州企业网站公司,越南网络公司排名,网站开发软件工程师,升降平台找企汇优做网站推广题目 跟39.组合总数、322.零钱兑换题目很类似。
法1#xff1a;背包DP#xff0c;最优解法 解释如下#xff1a; 0 1 2 3 4 5(背包容量)1 0 0 0 0 0 没有硬币的时候#xff09;
0 1 2 3 4 5(背包容量)
1 1 1 1 1 1 1
0 1 2 3 4 5(背包容量)
1 …题目 跟39.组合总数、322.零钱兑换题目很类似。
法1背包DP最优解法 解释如下 0 1 2 3 4 5(背包容量)1 0 0 0 0 0 没有硬币的时候
0 1 2 3 4 5(背包容量)
1 1 1 1 1 1 1
0 1 2 3 4 5(背包容量)
1 1 1 1 1 1 1
2 2 2 3 3
有了面值为2的硬币后哎我就是不用所以方案数还是dp[j]种
但是我如果用了那我看看在放入这枚硬币前也就是背包容量为[j-coins[i]]的时候有几种方案;
两种情况加起来所以就是 dp[j] dp[j]dp[j-coins[i]];
0 1 2 3 4 5(背包容量)
1 1 1 1 1 1 1
2 2 2 3 3
5 4class Solution {public int change(int amount, int[] coins) {int[] dp new int[amount 1]; // dp[i]表示金额之和等于i的硬币组合数目标是求 dp[amount]dp[0] 1;for (int coin : coins) {for (int i coin; i amount; i) {dp[i] dp[i - coin];}}return dp[amount];}
}法2回溯DFS基本方法
这道题目会超时
class Solution {public int ans 0;public int change(int amount, int[] coins) {int n coins.length;if (n 0) {return 0;}dfs(coins, 0, amount);return ans;}public void dfs(int[] coins, int startIndex, int target) {if (startIndex coins.length target ! 0) {return;}if (target 0) {ans;return;}dfs(coins, startIndex 1, target); // 不选startIndexif (target coins[startIndex]) { // 选择startIndexdfs(coins, startIndex, target - coins[startIndex]);}}
}
