我是靠谱客的博主 甜蜜大碗,这篇文章主要介绍Leetcode 518 零钱兑换 II (dp背包方案数),现在分享给大家,希望可以做个参考。

 dp方程的推导过程如下:

        // dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i]] + dp[i-1][j-2coins[i]] + ...

        // dp[i][j-coins[i]] = dp[i-1][j-coins[i]]+ ... + 

        // dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution { public: int change(int amount, vector<int>& coins) { int n = coins.size(); vector<vector<int>> dp(n + 1, vector<int>(amount + 1)); dp[0][0] = 1; for(int i = 1; i <= n; i++) { for(int j = 0; j <= amount; j++) { if(j >= coins[i - 1]) { dp[i][j] = dp[i - 1][j] + dp[i][j-coins[i - 1]]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][amount]; } };

二维优化到一维:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution { public: int change(int amount, vector<int>& coins) { int n = coins.size(); vector<int> dp(amount + 1); dp[0] = 1; for(auto coin : coins) { for(int j = 1; j <= amount; j++) { if(j >= coin) { dp[j] += dp[j - coin]; } } } return dp[amount]; } };

 

 

 

 

最后

以上就是甜蜜大碗最近收集整理的关于Leetcode 518 零钱兑换 II (dp背包方案数)的全部内容,更多相关Leetcode内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(94)

评论列表共有 0 条评论

立即
投稿
返回
顶部