IT源码网

零钱兑换讲解

flyfish 2020年10月22日 编程语言 294 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 之后,虽然还会有奇葩情况,但是绝大部分普通情况就可以疯狂剪枝了

 

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

nginx变量名规则讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。