[LeetCode] 322、零钱兑换

题目描述给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。你可以认为每种硬币的数量是无限的示例输入:coins[1,2,5],amount11输出:3解释:11551解题思路大佬在这里有一个动态规划套路详解吐血推荐。动态规划遵循一套固定的流程递归的暴力解法 - 带备忘录的递归解法 - 非递归的动态规划解法。千万不要看不起暴力解动态规划问题最困难的就是写出状态转移方程即这个暴力解。优化方法无非是用备忘录或者 DP table再无奥妙可言。“动态规划”在本质上其实还是“搜索”并且是“记忆化搜索”。“搜索”类问题我们还是应该先画“递归树”分析由递归树我们可以分析得到此问题有很多重复的子问题所以我们应该考虑通过“记忆化搜索”或者“dp table”来解决。ps看到此题的第一反应是用贪心算法但是贪心策略在这里并不适用原因在于贪心算法解决此题时鼠目寸光。参考代码// 自底向上的动态规划classSolution{public:intcoinChange(vectorintcoins,intamount){vectorvectorintdp(coins.size()1,vectorint(amount1,INT_MAX));// 这里用 INT_MAX 代表凑不成// 初始化dp[i][0] 表示用前 i 种硬币凑出金额 0 所需的最少硬币数答案显然是 0即一个硬币也不用for(inti0;icoins.size();i){dp[i][0]0;}for(inti1;icoins.size();i){for(intj1;jamount;j){dp[i][j]dp[i-1][j];if(j-coins[i-1]0dp[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];}};问题动态规划解法中怎么体现“每种硬币的数量是无限的”上述代码可以优化成一维数据这里暂时先不写了。