1. 题⽬链接：322. 零钱兑换
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] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。
这⾥教给⼤家⼀个技巧，就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 ⾥⾯的 i - 1 变成 i 即可。
3. 初始化：
初始化第⼀⾏即可。
这⾥因为取 min ，所以我们可以把⽆效的地⽅设置成⽆穷⼤ (0x3f3f3f3f)
因为这⾥要求正好凑成总和为 j ，因此，需要把第⼀⾏除了第⼀个位置的元素，都设置成⽆穷⼤。
4. 填表顺序：
根据「状态转移⽅程」，我们仅需「从上往下」填表即可。
5. 返回值：
根据「状态表⽰」，返回 dp[n][V] 。但是要特判⼀下，因为有可能凑不到
C++ 优化前的算法代码：
#define N 0x3f3f3f3f
class Solution
{
public:
int coinChange(vector<int>& coins, int amount)
{
//建表
int m=coins.size(),n=amount;
vector<vector<int>>dp(m+1,vector<int>(n+1));
//初始化
for(int i=1;i<=n;i++)
{
dp[0][i]=N;
}
//填表
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//不选
dp[i][j]=dp[i-1][j];
//选
//因为完全背包此处判断的是dp表同一行的状态
//使得dp[i][j]不存在时也会进入判断，故将选不到的状态定为极大值
if(j-coins[i-1]>=0&&dp[i][j-coins[i-1]]!=N)
{
dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
}
}
}
//返回值
return ((dp[m][n] == N) ? -1 : dp[m][n]);
}
};C++ 空间优化后的算法代码：
#define N 0x3f3f3f3f
class Solution
{
public:
int coinChange(vector<int>& coins, int amount)
{
//建表
int m=coins.size(),n=amount;
vector<int>dp(n+1);
//初始化
for(int i=1;i<=n;i++)
{
dp[i]=N;
}
//填表
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//因为完全背包此处判断的是dp表同一行的状态
//使得dp[i][j]不存在时也会进入判断，故将选不到的状态定为极大值
if(j-coins[i-1]>=0&&dp[j-coins[i-1]]!=N)
{
dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
}
}
}
//返回值
return ((dp[n] == N) ? -1 : dp[n]);
}
};Java 优化前算法代码：
class Solution
{
public int coinChange(int[] coins, int amount)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = coins.length, INF = 0x3f3f3f3f;
int[][] dp = new int[n + 1][amount + 1];
for (int j = 1; j <= amount; j++) dp[0][j] = INF;
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][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
}
return dp[n][amount] >= INF ? -1 : dp[n][amount];
}
}Java 空间优化后的算法代码：
class Solution
{
public int coinChange(int[] coins, int amount)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = coins.length, INF = 0x3f3f3f3f;
int[] dp = new int[amount + 1];
for (int j = 1; j <= amount; j++) dp[j] = INF;
for (int i = 1; i <= n; i++)
for (int j = coins[i - 1]; j <= amount; j++)
dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
return dp[amount] >= INF ? -1 : dp[amount];
}
}