动态规划-完全背包问题——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.优化