动态规划-完全背包问题——518.零钱兑换II
1.题目解析
建议先看 322.零钱兑换可以 更加轻松的理解本题
题目来源
518.零钱兑换——力扣
测试用例
2.算法原理
1.状态表示
本题要求返回所有情况，所以dp值就代表所有的方法数，即
dp[i][j]：在[1,i]个硬币中选择不同面值的硬币，此时面值总和恰好为j时所有的选择方法数
2.状态转移方程
3.初始化
4.填表顺序
从上到下，每一行从左到右
5.返回值
返回最后一个位置的值
3.实战代码
class Solution {
public:
int change(int amount, vector<int>& coins)
{
int n = coins.size();
vector<vector<double>> dp(n+1,vector<double>(amount+1));
dp[0][0] = 1;
for(int i = 1;i <= n;i++)
{
for(int j = 0;j <= amount;j++)
{
dp[i][j] += dp[i-1][j];
if(j >= coins[i-1] && dp[i-1][j-coins[i-1]] != -1)
{
dp[i][j] += dp[i][j-coins[i-1]];
}
}
}
return dp[n][amount];
}
};代码解析
4.优化
原文地址：https://blog.csdn.net/2301_80689220/article/details/143825041
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！