【面试经典150 | 动态规划】零钱兑换-Toy模板网

这篇具有很好参考价值的文章主要介绍了【面试经典150 | 动态规划】零钱兑换。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【动态规划】【数组】

题目来源

322. 零钱兑换

解题思路

方法一：动态规划

定义状态

dp[i] 表示凑成总金额的最少硬币个数。

状态转移

从小到大枚举要凑成的金额 i，如果当前的金额可以使用面额数组中的某个面额 coin 凑成总金额的一部分，则可以更新

$d p [i] = min (d p [i], d p [i - co in] + 1)$

base case

dp[0] = 0，表示凑成总金额 0 的硬币数量为 0。

最后返回

dp[amount]，表示凑成总金额 amount 的最少硬币个数。注意需要判断面额数组是否可以凑成指定的总金额。

实现代码

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

        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (const auto coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i-coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount]; 
    }
};

复杂度分析

时间复杂度： $O (S n)$ ， $S$ 是题目给定的需要凑成的总金额数， $n$ 是面额数。我们一共需要计算 $O (S)$ 个状态，每个状态需要枚举 $n$ 个面额进行状态转移，所以时间复杂度为 $O (S n)$ 。