题目链接
LeetCode 面试题 08.11. 硬币[1]
题目描述
给定数量不限的硬币，币值为 25 分、10 分、5 分和 1 分，编写代码计算 n 分有几种表示法。(结果可能会很大，你需要将结果模上 1000000007)
说明：
0 <= n (总金额) <= 1000000
示例1
输入：n = 5输出:2解释：有两种方式可以凑成总金额:5=55=1+1+1+1+1
示例2
输入：n = 10输出:4解释：有四种方式可以凑成总金额:10=1010=5+510=5+1+1+1+1+110=1+1+1+1+1+1+1+1+1+1
题解
朴素想法（错误）
动态规划 1
动态规划 2（超时）
转移方程优化
神奇的地方来了，上面两种方法，全部可以优化为同一个式子，仔细看好了。
动态规划 1：
动态规划 2：
最终形式：
空间优化
数学法
代码
动态规划 1（c++）
classSolution { public: typedeflonglongll; staticconstllmod=1e9+7; staticconstintN=1000010; staticconstintM=4; lldp[M][N]; intp[M] = {1, 5, 10, 25}; intwaysToChange(intn) { memset(dp, 0, sizeofdp); for (inti=0; i<M; ++i) dp[i][0] =1; for (inti=0; i<M; ++i) { for (intj=1; j<=n; ++j) { for (intk=0; k<=i; ++k) { if (j>=p[k]) { (dp[i][j] +=dp[k][j-p[k]]) %=mod; } } } } returndp[M-1][n]; } };
动态规划 2（超时）（c++）
classSolution { public: typedeflonglongll; staticconstllmod=1e9+7; staticconstintN=1000010; staticconstintM=4; lldp[M][N]; intp[M] = {1, 5, 10, 25}; intwaysToChange(intn) { memset(dp, 0, sizeofdp); for (inti=0; i<M; ++i) dp[i][0] =1; for (inti=0; i<=n/p[0]; ++i) dp[0][i*p[0]] =1; for (inti=1; i<M; ++i) { for (intj=1; j<=n; ++j) { for (intk=0; k<=j/p[i]; ++k) { (dp[i][j] +=dp[i-1][j-k*p[i]]) %=mod; } } } returndp[M-1][n]; } };
转移方程优化（c++）
classSolution { public: typedeflonglongll; staticconstllmod=1e9+7; staticconstintN=1000010; staticconstintM=4; lldp[M][N]; intp[M] = {1, 5, 10, 25}; intwaysToChange(intn) { memset(dp, 0, sizeofdp); for (inti=0; i<M; ++i) dp[i][0] =1; for (inti=0; i<=n/p[0]; ++i) dp[0][i*p[0]] =1; for (inti=1; i<M; ++i) { for (intj=1; j<=n; ++j) { dp[i][j] =dp[i-1][j]; if (j>=p[i]) (dp[i][j] +=dp[i][j-p[i]]) %=mod; } } returndp[M-1][n]; } };
空间优化（c++）
classSolution { public: typedeflonglongll; staticconstllmod=1e9+7; staticconstintN=1000010; staticconstintM=4; lldp[N]; intp[M] = {1, 5, 10, 25}; intwaysToChange(intn) { memset(dp, 0, sizeofdp); dp[0] =1; for (intj=0; j<M; ++j) { for (inti=1; i<=n; ++i) { if (i>=p[j]) { (dp[i] +=dp[i-p[j]]) %=mod; } } } returndp[n]; } };
数学法（c++）
classSolution { public: typedeflonglongll; staticconstllmod=1e9+7; intwaysToChange(intn) { llres=0; for (inti=0; i<=n/25; ++i) { llr=n-25*i; llx=r/10, y=r/5; (res+= (x+1) * (y-x+1)) %=mod; } returnres; } };
参考资料
[1]
LeetCode 面试题 08.11. 硬币: https://leetcode-cn.com/problems/coin-lcci/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
