[LeetCode] 322、零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例：

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
           

解题思路

大佬在这里有一个动态规划套路详解，吐血推荐。

动态规划遵循一套固定的流程：递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法。

千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。

“动态规划”在本质上其实还是“搜索”，并且是“记忆化搜索”。“搜索”类问题，我们还是应该先画“递归树”分析：

由递归树我们可以分析得到，此问题有很多重复的子问题，所以我们应该考虑通过“记忆化搜索”或者“dp table”来解决。

ps：看到此题的第一反应是用贪心算法，但是贪心策略在这里并不适用，原因在于贪心算法解决此题时鼠目寸光。

参考代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;  // 凑0元需要0个硬币
        for(int money = 1; money <= amount; money++){
            for(auto coin: coins){
                if(money - coin >= 0 && dp[money - coin] != INT_MAX)  // 注意这里的判断条件
                    dp[money] = min(dp[money], dp[money - coin] + 1);  // 别忘+1
            }
        }
        
        return dp[amount] == INT_MAX? -1: dp[amount];
    }
};