1. 题⽬链接：518. 零钱兑换 II
2. 题⽬描述：
3. 解法（动态规划）：
算法思路：
先将问题「转化」成我们熟悉的题型。
i. 在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率是背包模型；
ii. 由于每⼀个物品都是⽆限多个的，因此是⼀个「完全背包」问题。接下来的分析就是基于「完全背包」的⽅式来的。
1. 状态表⽰：
dp[i][j] 表⽰：从前 i 个硬币中挑选，总和正好等于 j ，⼀共有多少种选法。
2. 状态转移⽅程：
线性 dp 状态转移⽅程分析⽅式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：
i. 选 0 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j 。此时最少的硬币个数为 dp[i - 1][j] ；
ii. 选 1 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j -v[i] 。因为挑选了⼀个 i 硬币，此时最少的硬币个数为 dp[i - 1][j -coins[i]] + 1 ；
iii. 选 2 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j- 2 * coins 。因为挑选了两个 i 硬币，此时最少的硬币个数为 dp[i - 1][j -2 * coins[i]] + 2 ；
iv. ......
结合我们在完全背包⾥⾯的「优化思路」，我们最终得到的状态转移⽅程为：
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] + 1 。
这⾥教给⼤家⼀个技巧，就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 ⾥⾯的 i - 1 变成 i 即可。
3. 初始化：
初始化第⼀⾏即可。
第⼀⾏表⽰没有物品，没有物品正好能凑能和为 0 的情况。因此 dp[0][0] = 1 ，其余位置都
是 0 种情况。
4. 填表顺序：
根据「状态转移⽅程」，我们仅需「从上往下」填表即可。
5. 返回值：
根据「状态表⽰」，返回 dp[n][V]
C++ 空间优化后的算法代码：
class Solution
{
public:
int change(int amount, vector<int>& coins)
{
//建表
int m=coins.size(),n=amount;
vector<vector<double>>dp(m+1,vector<double>(n+1));
//初始化
dp[0][0]=1;
//填表
for(int i=1;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
//不选
dp[i][j]=dp[i-1][j];
//选
if(j-coins[i-1]>=0)
{
dp[i][j]+=(dp[i][j-coins[i-1]]);
}
}
}
//返回值
return dp[m][n];
}
};Java 空间优化后的算法代码：
class Solution
{
public int change(int amount, int[] coins)
{
// 空间优化
int[] dp = new int[amount + 1]; // 建表
dp[0] = 1; // 初始化
for (int x : coins) // 拿出物品
for (int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置
dp[j] += dp[j - x];
return dp[amount];
}
}