每日OJ题_完全背包③_力扣518. 零钱兑换 II

目录

力扣518. 零钱兑换 II

问题解析

解析代码

优化代码（滚动数组）

---

力扣518. 零钱兑换 II

518. 零钱兑换 II

难度 中等

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

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

---

问题解析

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

状态转移方程：

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

状态表示： 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] = 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]] = 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] = 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，初始化第一行即可。第一行表示没有物品，没有物品正好能凑能和为 0 的情况。因此 dp[0][0] = 1 ，其余位置都是 0 种情况。

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

返回值： 根据状态表示，返回 dp[n][amount] 。

---

解析代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // dp[i][j]表示：从前i个硬币中挑选，总和正好等于j ，一共有多少种选法
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 0; j <= amount; ++j)
            {
                if(j >= coins[i - 1])
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][amount];
    }
};

---

优化代码（滚动数组）

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

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

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

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

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount + 1, 0); // 滚动数组优化
        dp[0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = coins[i - 1]; j <= amount; ++j)
            {
                dp[j] = dp[j] + dp[j - coins[i - 1]];
            }
        }
        return dp[amount];
    }
};