[LeetCode] 322、零钱兑换

题目描述

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

示例：

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

解题思路

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

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

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

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

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

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

参考代码

// 自底向上的动态规划classSolution{public:intcoinChange(vector<int>&coins,intamount){vector<vector<int>>dp(coins.size()+1,vector<int>(amount+1,INT_MAX));// 这里用 INT_MAX 代表凑不成// 初始化：dp[i][0] 表示用前 i 种硬币凑出金额 0 所需的最少硬币数，答案显然是 0（即一个硬币也不用）for(inti=0;i<=coins.size();i++){dp[i][0]=0;}for(inti=1;i<=coins.size();i++){for(intj=1;j<=amount;j++){dp[i][j]=dp[i-1][j];if(j-coins[i-1]>=0&&dp[i][j-coins[i-1]]!=INT_MAX){dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1);// 完全背包}}}returndp[coins.size()][amount]==INT_MAX?-1:dp[coins.size()][amount];}};

问题：动态规划解法中，怎么体现“每种硬币的数量是无限的”？

上述代码可以优化成一维数据，这里暂时先不写了。