每日OJ题_完全背包②_力扣322. 零钱兑换

目录

力扣322. 零钱兑换

问题解析

解析代码

优化代码（滚动数组）

---

力扣322. 零钱兑换

322. 零钱兑换

难度 中等

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11

输出：3

解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3

输出：-1

示例 3：

输入：coins = [1], amount = 0

输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
 
    }
};

---

问题解析

先看能不能将问题转化成我们熟悉的题型。

• 在一些物品中挑选一些出来，然后在满足某个限定条件下，解决一些问题，大概率是背包模型；
• 由于每一个物品都是无限多个的，因此是一个完全背包问题。接下来的分析就是基于完全背包的方式来

状态表示： dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于 j ，所有的选法中，最少的硬币个 数。

状态转移方程：

        线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论。但是最后一个物品能选很多个，因此需要分很多情况：

• 选 0 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j 。 此时最少的硬币个数为 dp[i - 1][j] 
• 选 1 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - v[i] 。因为挑选了一个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - coins[i]] + 1 ;
• 选 2 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - 2 * coins 。因为挑选了两个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - 2 * coins[i]] + 2 ;
• ......

综上，状态转移方程为：

dp[i][j]=min(dp[i - 1][j], dp[i - 1][j - coins[i]] + 1, dp[i - 1][j - 2*coins[i]] + 2 ......)

        这时发现，计算一个状态的时候，需要一个循环才能搞定的时候，我们要想到去优化。优化的方向就是用一个或者两个状态来表示这一堆的状态，通常就是用数学的方式做一下等价替换。

        发现第二维是有规律的变化的，因此去看看 dp[i][j - v[i]] 这个状态： dp[i][j - v[i]]=min(dp[i - 1][j - coins[i]] + 1,dp[i - 1][j - 2*coins[i]]] + 2,dp[i - 1] [j - 3*coins[i]] + 3......)

        因此可以修改我们的状态转移方程为： dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。（j >= coins[i] ， dp[i][j - coins[i]] 存在 。）（如果初始化多开一行一列，找coins数组要减一）

有个技巧，就是相当于把第二种情况 dp[i - 1][j - coins[i]] + 1 ⾥ ⾯的 i - 1 变成 i 即可。

初始化： dp[0[0]为0，初始化第一行即可。 这里因为取 min ，所以可以把无效的地方设置成无穷大 （0x3f3f3f3f） 因为这里要求正好凑成总和为 j ，因此，需要把第一行除了第一个位置的元素，都设置成无穷大。

填表顺序： 根据状态转移方程，仅需从上往下填表。

返回值： 根据状态表示，返回 dp[n][amount] 。由于最后可能凑不成总数为 amount 的情况，因此返回之前需要特判一下。

---

解析代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        const int INF = 0x3f3f3f3f; // 无穷大的一半
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INF));
        // dp[i][j]表示：从前i个硬币中挑选，总和正好等于j，所有的选法中，最少的硬币个数
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 0; j <= amount; ++j)
            {
                if(j >= coins[i - 1])
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][amount] >= INF ? -1 : dp[n][amount];
    }
};

---

优化代码（滚动数组）

背包问题基本上都是利用滚动数组来做空间上的优化：

1. 利用滚动数组优化。
2. 直接在原始代码上修改。

在完全背包问题中，优化的结果为：

1. 仅需删掉所有的横坐标。

（填一行数组的值的时候要用到前面新填的值，所以依旧是从左往右遍历，01背包是从右往左）

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        const int INF = 0x3f3f3f3f; // 无穷大的一半
        int n = coins.size();
        vector<int> dp(amount + 1, INF);
        dp[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = coins[i - 1]; j <= amount; ++j)
            {
                dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[amount] >= INF ? -1 : dp[amount];
    }
};