LeetCode #322:Coin Change(零钱兑换)

题目描述

本题是运用完全背包的思想来求一个最小值问题。区别于 01 背包,完全背包问题就是每个物品可以不限个数地放入背包,相应的递推公式也会发生变化。

我们先考虑二维 dp 数组的情况,设状态 dp[i][j] 为考虑前 0-i 个钱币,凑足总额为 j 所需钱币的最少个数,可得出如下递推公式:

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-1][j-k*coins[i]]+k, ...) // ①

即要么不使用面值为 i的硬币,要么使用 1个、2个、3个…… k个……面值为 i的硬币

我们将上式的 j 替换为 j-coins[i],得:

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

我们不难发现,① 式 min 中 dp[i-1][j] 后面的部分正好是 ② 式 + 1,将 ② 式代入 ① 式,得:

dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]]+1) // ③

同 01 背包问题一样,我们对 dp 数组运用滚动数组的方法压缩到一维,最终的递推公式如下:

dp[j] = min(dp[j], dp[j-coins[i]]+1) // ④

虽然 ④ 式和 01 背包问题优化后的式子并无二致,但为了体现出优化前 ③ 式的状态转移关系,我们在遍历一维 dp 数组时需要从前往后(而不是 01 背包从后往前)遍历,这样就保证了 dp[j-coins[i]] 永远是先于 dp[j] 计算的。

代码实现如下:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount + 1, amount + 1); // dp数组初始化为amount+1,作为最大值,方便下面取min的状态转移
        dp[0] = 0; // 显然dp[0]初始化为0
        for(int i = 0; i < n; i ++) {
            for(int j = coins[i]; j <= amount; j ++) { // 注意完全背包的内层循环是从前往后遍历的
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount]; // 若dp[amount]为amount+1,说明条件给出的硬币面额无法凑出amount
    }
};

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注