题目及其链接如下:
题目:硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007)
示例1:
输入: n = 5
输出:2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:
输入: n = 10
输出:4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明:无。
注意:
你可以假设:
0 <= n (总金额) <= 1000000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/coin-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
leetcode官方给出的参考解答及链接如下:
方法一,动态规划的C++代码:
C++
class Solution {
private:
static constexpr int mod = 1000000007;
static constexpr int coins[4] = {25, 10, 5, 1};
public:
int waysToChange(int n) {
vector<int> f(n + 1);
f[0] = 1;
for (int c = 0; c < 4; ++c) {
int coin = coins[c];
for (int i = coin; i <= n; ++i) {
f[i] = (f[i] + f[i - coin]) % mod;
}
}
return f[n];
}
};
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/coin-lcci/solution/ying-bi-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
链接:官方给出的参考解答
感想·总结
【这段为废话】我没有学过相关的知识,背包问题这个名词也几乎是第一次听到。官网给出的参考解答有两种方法,第一种是背包问题,第二种是直接就此问题数学推导的,我也没有看。其他的的题解也大都是背包问题,有单讲这一题的,也有系统讲解的,我也去第一大学习网站——小破站搜了几个视频看,没有看完。这些学习资料都挺好的,只不过我看不懂。/我太南了 只好对着这几行代码,拿起砝码,硬着头皮想它的理解方法。
【以下是正餐】
我们来分析一下题目。题目说,钱币面值有4种,分别是1,5,10,25。题目要问的是,在指定的输入数值价格n下,我有几种组合钱币的方式。
第一反应是,类似于中学实验里头加砝码的办法,砝码重量一定,数量不限的情况下,先加大的砝码,直到超过了要测量的重量,就拿下这个大的加小一点的砝码。一次加小的,知道天平达到平衡。同样的方法,我们也可以用来做这个问题。不过得到的只是其中一种方法。而我们要求的不是可行的方法,是问共有几种可行的组合方法使这个天平达到平衡。
(这个硬币问题和砝码的问题其实是一样的。如果跟我一样,把这个问题想象成砝码问题,能过够些微帮助一下理解这几行神奇的代码的话,可以这么想。否者,就直接把下文的砝码换成硬币就行。)
于是我们很容易可以想到,在加砝码的过程中,其实大的可以用小的来替换,比如加一个10g的砝码其实和加2个5g的或者10个1g的砝码是一样的。而所有的组合的可能性,可以先考虑一种重量的砝码有多少种可能性,再多加一种砝码,共考虑两种砝码,加上新增的可能性,依次考虑加入新的砝码,加上新增的可能的种数,知道考虑完所有的4种重量的砝码。
设一个存放可能的组合数量的数组f[n+1]。最外面一层循环,依次考虑一种新的面值,循环体内加上因此而新增的组合方式。
每考虑一个新的面值的硬币,小于该面值的n值,组合方式数量不会增加。只有大于等于该面值的n值才会增加。故循环体内需要一个内循环,依次考虑从面值到n值的价格。比如,如果输入的价格n是13的话,外层循环循环到10的时候,内层循环需要考虑从10到13的数量,而不需要考虑0到9。外层循环循环到25的时候,0到13都不用考虑,而内层循环条件为25到13,符合。
给代码加上注释,如下:
class Solution {
private:
static constexpr int mod = 1000000007; //模上这个数,可以防止大数溢出。总之具体的原因可以百度。读代码的时候可以暂时忽略这个操作。
static constexpr int coins[4] = {25, 10, 5, 1};//硬币的四种面值
public:
int waysToChange(int n) {
vector<int> f(n + 1); //f(i)为组成i的值的组合方式数。
f[0] = 1; //给f(0)初始化为1,以此来产生f(i), I>0, 的值。
//下面开始大循环,依次考虑增加25,10,5,1面值的硬币,增加因此而增加的组合方式数。
for (int c = 0; c < 4; ++c) {
int coin = coins[c];
for (int i = coin; i <= n; ++i) { // 开始内循环,从至少是该面值数大小开始,一直到输入的数n。
f[i] = (f[i] + f[i - coin]) % mod;
}
}
return f[n];
}
};
而内层循环种,忽略掉取模防溢出的话,就是
f[i] = (f[i] + f[i - coin])
关于这个式子,可以仔细想一想,从可能用到新增的硬币的数coin开始,逐一递增,直到输入的数n,依次加上比该数值小coin的数值的可能性数量。因为f(0)设置为1,所以每一次的内外循环,都能逐次增加新的组合方式数量。如果凭空想不明白的,可以调试程序,或是在稿纸上自己演算一下,很容易就明白了。
以上,如有错误,还请不吝赐教。