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
18class 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
16class 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内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复