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];
	}
}