【经典算法题】零钱兑换

Leetcode 0322 零钱兑换

题目描述：Leetcode 0322 零钱兑换

分析

• 本题的考点：背包问题。

• 完全背包问题，amout为容量；物品体积为coins[i]，价值为1。

• 本题和Leetcode 0279 完全平方数十分类似，可以参考LC279的分析。

• 注意本题和Leetcode 0518 零钱兑换 II的区别，LC518让求得是体积恰好是m的方案数，本题求的是体积恰好是m需要用的最少硬币数。

代码

• C++

class Solution {
    
public:
    int coinChange(vector<int> &coins, int m) {
    

        vector<int> f(m + 1, 1e8);
        f[0] = 0;
        for (auto v : coins)
            for (int j = v; j <= m; j++)
                f[j] = min(f[j], f[j - v] + 1);
        if (f[m] == 1e8) return -1;
        return f[m];
    }
};

• Java

class Solution {
    
    public int coinChange(int[] coins, int m) {
    

        int[] dp = new int[m + 1];
        Arrays.fill(dp, m + 1);
        dp[0] = 0;
        for (int v : coins)
            for (int j = v; j <= m; j++)
                dp[j] = Math.min(dp[j], dp[j - v] + 1);
        return dp[m] == m + 1 ? -1 : dp[m];
    }
}

时空复杂度分析

• 时间复杂度：$O(n\times m)$，n为不同面值的硬币数，m为总金额。

• 空间复杂度：$O(m)$。

Leetcode 0518 零钱兑换 II

题目描述：Leetcode 0518 零钱兑换 II

分析

• 本题的考点：背包问题。

• 本题将amout简记为m。问题是：给我们一个容量为m的背包，每个物品的体积由coins给出，每个物品可以使用无数次，问恰好装满背包的方案数。

• 本题就是一个完全背包问题。关于背包问题可以参考：背包问题（背包九讲）。

• 注意本题和Leetcode 0322 零钱兑换的区别，LC322让求的是体积恰好是m需要用的最少硬币数，本题求得是体积恰好是m的方案数，还有一类最常规的让求最大价值（体积不超过m的最大价值，体积恰好是m的最大价值，体积不小于m的最小耗费）。

• 另外注意本题和Leetcode 0377 组合总和 Ⅳ，和本题的唯一区别在于，认为1,2和2,1是不同的方案。因此LC377先循环体积，再循环物品，这样对于每个体积，可以根据最后一个放入的数据分为n类，因此可以实现不同顺序是不同方案。完全背包最初的分析（见背包九讲的分析），是每个物品放置几个数据，因此不同顺序认为是相同方案。

代码

• C++

class Solution {
    
public:
    int change(int m, vector<int>& coins) {
    
        vector<int> f(m + 1);
        f[0] = 1;
        for (int v : coins)
            for (int j = v; j <= m; j++)
                f[j] += f[j - v];
        return f[m];
    }
};

• Java

class Solution {
    
    public int change(int m, int[] coins) {
    
        int[] f = new int[m + 1];
        f[0] = 1;
        for (int v : coins)
            for (int j = v; j <= m; j++)
                f[j] += f[j - v];
        return f[m];
    }
}

• Python

class Solution:
    def change(self, m: int, coins: List[int]) -> int:
        f = [0 for _ in range(m + 1)]
        f[0] = 1
        for v in coins:
            for j in range(v, m + 1):
                f[j] += f[j - v];
        return f[m]

时空复杂度分析

• 时间复杂度：$O(n\times m)$，n为数组长度，m是题目中的amout。

• 空间复杂度：$O(n\times m)$。