国外市场网站推广公司,电子商务经营范围有哪些?,镇海区建设交通局网站进不去了,小型网站网站建设需要文章目录1. 题目2. 解题1. 题目
硬币。给定数量不限的硬币#xff0c;币值为25分、10分、5分和1分#xff0c;编写代码计算 n 分有几种表示法。(结果可能会很大#xff0c;你需要将结果模上1000000007)
示例1:输入: n 5输出#xff1a;2解释: 有两种方式可以凑成总金额:…
文章目录1. 题目2. 解题1. 题目
硬币。给定数量不限的硬币币值为25分、10分、5分和1分编写代码计算 n 分有几种表示法。(结果可能会很大你需要将结果模上1000000007)
示例1:输入: n 5输出2解释: 有两种方式可以凑成总金额:
55
511111示例2:输入: n 10输出4解释: 有四种方式可以凑成总金额:
1010
1055
10511111
101111111111说明
0 n (总金额) 1000000来源力扣LeetCode 链接https://leetcode-cn.com/problems/coin-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
错误解法下面解法dp[6] 3, 1*6, 15, 51
class Solution {
public:int waysToChange(int n) {int coin[4] {1,5,10,25};vectorint dp(n1,0);dp[0] 1;int i, j;for(i 0; i n; i){if(dp[i]! 0)for(j 0; j 4; j)//coin在内层循环错误{if(icoin[j] n)dp[icoin[j]] (dp[icoin[j]] dp[i])%1000000007;}}return dp[n]%1000000007;}
};跟顺序无关硬币数量无限先只拿一种硬币有多少种可能的状态在上面状态下拿第二种硬币得到新的状态
0 1 2 3 4 5 6 7 8 9 10
----------------------coin[4] {1,5,10,25}
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 2 2 2 2 2 3
1 1 1 1 1 2 2 2 2 2 4
1 1 1 1 1 2 2 2 2 2 4 class Solution {
public:int waysToChange(int n) {int coin[4] {1,5,10,25};vectorint dp(n1,0);dp[0] 1;int i, j, money;for(i 0; i 4; i){for(j 0; j n; j){if(dp[j]! 0 jcoin[i] n)dp[jcoin[i]] (dp[jcoin[i]] dp[j])%1000000007;}}return dp[n]%1000000007;}
};
