零钱兑换分析

哈哈 阅读:396 2020-10-22 16:40:32 评论:0

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

示例 1:

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

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

j解:这题有两种解法,回溯法和动态规划

动态规划

我们采用自下而上的方式进行思考。仍定义 F(i)F(i) 为组成金额 ii 所需最少的硬币数量,假设在计算 F(i)F(i) 之前,我们已经计算出 F(0)-F(i-1)F(0)−F(i−1) 的答案。 则 F(i)F(i) 对应的转移方程应为

F(i)=minF(icj)+1

其中 cj代表的是第 jj 枚硬币的面值,即我们枚举最后一枚硬币面额是 cj


那么需要从 i-cj

这个金额的状态 F(i-cj)

 转移过来,再算上枚举的这枚硬币数量 11 的贡献,由于要硬币数量最少,所以 F(i)为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。

通过这道题

这里插一下动态规划里最重要的状态转移

「状态转移方程」这个名词,实际上就是描述问题结构的数学形式:

f(n) = \begin{cases} 1, n = 1, 2 \\ f(n - 1) + f(n - 2), n > 2 \end{cases}
f(n)={
1,n=1,2
f(n−1)+f(n−2),n>2

//////////////////////////////////////

为啥叫「状态转移方程」?为了听起来高端。你把 f(n) 想做一个状态 n,这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来,这就叫状态转移,仅此而已。

你会发现,上面的几种解法中的所有操作,例如 return f(n - 1) + f(n - 2),dp[i] = dp[i - 1] + dp[i - 2],以及对备忘录或 DP table 的初始化操作,都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性,它是解决问题的核心。很容易发现,其实状态转移方程直接代表着暴力解法。

///////////////////////////////////////

class Solution { 
public: 
    int coinChange(vector<int>& coins, int amount) { 
        int MAX=amount+1; 
        vector<int> vec(amount+1,MAX); 
        vec[0]=0; 
        //f(n)=f(n-coins[i])+1; 
        for(int i=1;i<=amount;i++) 
        { 
            for(int j=0;j<coins.size();j++) 
            { 
                //当前币值比要求的第i个最小货币数都大,因为货币最小为1,可以跳过 
                if(i-coins[j]<0) 
                { 
                    continue; 
                } 
                vec[i]=min(vec[i],vec[i-coins[j]]+1); 
            } 
        } 
        return vec[amount]>amount?-1:vec[amount]; 
    } 
};

下面这个介绍回溯,我最开始也是回溯做的,但是在个别测试用例中超时,看一下别人做的。把某些情况快速跳过,会很快。

解题思路
贪心
11. 想要总硬币数最少,肯定是优先用大面值硬币,所以对 coins 按从大到小排序
12. 先丢大硬币,再丢会超过总额时,就可以递归下一层丢的是稍小面值的硬币

乘法对加法的加速
21. 优先丢大硬币进去尝试,也没必要一个一个丢,可以用乘法算一下最多能丢几个

k = amount / coins[c_index] 计算最大能投几个
amount - k * coins[c_index] 减去扔了 k 个硬币
count + k 加 k 个硬币

如果因为丢多了导致最后无法凑出总额,再回溯减少大硬币数量
最先找到的并不是最优解
31. 注意不是现实中发行的硬币,面值组合规划合理,会有奇葩情况
32. 考虑到有 [1,7,10] 这种用例,按照贪心思路 10 + 1 + 1 + 1 + 1 会比 7 + 7 更早找到
33. 所以还是需要把所有情况都递归完

ans 疯狂剪枝
41. 贪心虽然得不到最优解,但也不是没用的
42. 我们快速算出一个贪心的 ans 之后,虽然还会有奇葩情况,但是绝大部分普通情况就可以疯狂剪枝了

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

一个IT知识分享的公众号