已知正整数n,将其分为0到多个25、10、5、1这四个数的和。如n为11可分为一个10和一个1,或者分为两个5和一个1。返回n有多少种分法。保证n小于等于100000,请将答案Mod 1000000007以防止溢出。
测试样例:
6
返回:2
int fun(int n, int coin) { int nextcoin=0; switch(coin) { case 25: nextcoin=10; break; case 10: nextcoin=5; break; case 5: nextcoin=1; break; case 1: return 1; } int res=0; for(int i=0;i*coin<=n;i++) { res+=fun(n-i*coin, nextcoin)%1000000007; } return res%1000000007;//%1000000007 }
class Coins { public: int countWays(int n) { int coins[4]={1,5,10,25}; int dp[100001]={0}; dp[0]=1; for(int i=0;i<4;i++) for(int j=coins[i];j<=n;j++) dp[j] =(dp[j]+dp[j-coins[i]])%1000000007; return dp[n]; } };
//二维dp public int countWays(int n) { int A[] = {1, 5, 10, 25}, dp[][] = new int[A.length][n + 1]; for (int j = 0; j <= n; j++) { dp[0][j] = 1; } for (int i = 1; i < A.length; i++) { for (int j = 0; j <= n; j++) { int t = j - A[i]; if (t >= 0) { dp[i][j] = (dp[i - 1][j] + dp[i][t]) % 1000000007; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[A.length - 1][n]; } //一维dp public int countWays(int n) { int dp[] = new int[n + 1], i, A[] = {1, 5, 10, 25}; for (i = 0, dp[0] = 1; i < A.length; i++) { for (int j = A[i]; j <= n; j++) { dp[j] = (dp[j] + dp[j - A[i]]) % 1000000007; } } return dp[n]; }
dp[i][j]:总价值为i分的硬币总值中单个硬币最大值为j分的组合数 class Coins { #define MOD 1000000007 public: int countWays(int n) { vector<vector<int>> dp(n + 1, vector<int>(26, 0)); for (int i = 0; i <= n; ++i) dp[i][1] = 1; for (int i = 2; i <= n; ++i) { if (i >= 5) dp[i][5] = (dp[i - 5][5] + dp[i - 5][1]) % MOD; if (i >= 10) dp[i][10] = ((dp[i - 10][10] + dp[i - 10][5]) % MOD + dp[i - 10][1]) % MOD; if (i >= 25) dp[i][25] = ((dp[i - 25][25] + dp[i - 25][10]) % MOD + (dp[i - 25][5] + dp[i - 25][1]) % MOD) % MOD; } int res = dp[n][1]; res = (res + dp[n][5]) % MOD; res = (res + dp[n][10]) % MOD; res = (res + dp[n][25]) % MOD; return res; } };
# -*- coding:utf-8 -*- class Coins: def countWays(self, n): coins = [1, 5, 10, 25] dp = [0 for i in range(n + 1)] dp[0] = 1 for i in range(4): for j in range(coins[i], n + 1): dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007 return dp[n]
class Coins { public: int countWays(int n) { // write code here vector<vector<int>> dp(4,vector<int>(n+1,-1)); int coin[4]={1,5,10,25}; return helper(n,3,dp,coin); } int helper(int n,int i,vector<vector<int>> &dp,int coin[4]){ if(i==0){ dp[i][n]=1; return 1; } if(n==0){ dp[i][n]=1; return 1; } int ret=0; while(n>=0){//循环计算0个coin[i],1个coin[i],2个coin[i]...,并累加求和 if(dp[i][n]==-1)dp[i][n]=helper(n,i-1,dp,coin);//若计算过则不再计算 ret+=dp[i][n]; if(ret>=1000000007)ret%=1000000007; n-=coin[i]; } return ret; } };
请教各位,我的方法为什么不对 我的思路:这道题目类似上楼梯,斐波那契数列派生出来的问题 public class Coins { public int countWays(int n) { int result[] = new int[n]; result[0] = 1; for(int i = 0; i < n; i ++) { add(i, 1, result); add(i, 5, result); add(i, 10, result); add(i, 25, result); } return result[n - 1]; } private void add(int current, int value, int[] result) { if(current - value >= 0) { int tmp = (result[current] + result[current - value]) % 1000000007; result[current] = tmp; } } }
/** * 有数量不限的硬币,币值为25分、10分、5分和1分,请编写代码计算n分有几种表示法。 给定一个int n,请返回n分有几种表示法。保证n小于等于100000,为了防止溢出,请将答案Mod 1000000007。 */ public int countWays(int n) { // write code here int arr[] = {25,10,5,1}; int dp[][] = new int[arr.length][n+1]; for (int i = 0; i <arr.length; i++) { dp[i][0] = 1; } for (int j = 1; arr[0]*j<=n; j++) { dp[0][arr[0]*j] = 1; } for (int i = 1; i < arr.length; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j]%1000000007; dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]]%1000000007 : 0; } } return dp[3][n]%1000000007; }
import java.util.*; /* 思路:这题目看过去有点像奇怪的斐波拉契数列:f(2=f(1)+1,f(6)=f(5)+f(1),f(7)=f(6),直到f(10)=f(9)+f(1); f(11)=f(1)+f(6)+f(10),f(26)=f(1)+f(16)+f(21)+f(25); 然而递归超时了,GG,换一种思路,其实硬币的组成方式就是4种硬币都一次覆盖一遍这个数之后的数目,细细体会一下 比如只有1分的硬币,那是不是11分的硬币就只有1种组成方式,这时多了一种5分的硬币,那是不是原来6分的硬币这个时候加上5分就能组成11分 因此11分硬币此时的组成方式是原先的组成方式加上6分自己的组成方式 类推过去,将4种币值都给每个位置遍历一遍,累加到最后的数值就是那个硬币的组成方式 */ public class Coins { public int countWays(int n) { int c[] = new int[n+1]; c[0]=1;//这里算错了 其实0分也属于1种组成方式,即全都不要,而不是0种 int a[] ={1,5,10,25}; for(int i=0;i<a.length;i++){ for(int j=a[i];j<n+1;j++){ c[j]=(c[j]+c[j-a[i]])%1000000007; } } return c[n]; } } 运行时间:87ms 占用内存:13768k
//都用的动态规划的方法 //详细算法参考http://blog.csdn.net/qiaoqiao0609/article/details/50830992 //直接用二维数组实现没有复杂度优化 import java.util.*; public class Coins { public int countWays(int n) { int[] a = {1, 5, 10, 25}; int[][] dp = new int[5][n + 1]; for(int j=0;j<=4;j++){ dp[j][0]=1; } for(int i=1;i<5;i++){ for(int j=1;j<=n;j++){ if(j-a[i-1]>=0){ dp[i][j]=(dp[i-1][j]%1000000007+dp[i][j-a[i-1]]%1000000007)%1000000007; }else{ dp[i][j]=dp[i-1][j]; } } } return dp[4][n]; } } //用滚动数组实现,降低了空间复杂度 import java.util.*; public class Coins { public int countWays(int n) { // write code here int coins[]={1,5,10,25}; int sums[]=new int[100001]; sums[0]=1; for(int i=0;i<4;i++){ for(int j=0;j<=n;j++){ if((j-coins[i])>=0) sums[j]=(sums[j]+sums[j-coins[i]])%1000000007; } } return sums[n]; } }
public int countWays11(int n) { // write code here /* * 问题解析 首先如果只用一种硬币的话,那么只有一种解法 接下来,如果我在前一种硬币的基础上又用了一种硬币那么我的解法就变成两种了 好了 * 我们模拟下 首先我的硬币只有面值1 2 那么我要组合成面值为四 有多少种解法呢 1.我们只用面值1的硬币 那么就是 1 1 1 1 * 这里就有1种解了 2.接下来我们要用面值为2的硬币在用了面值1硬币的基础上 那么就得在 1 1 后用 2 此时已经有了2种解法了 * 3.那么此时采用了1个面值为2的硬币啊,按道理说我们是可以用两个面值为2的硬币的,所以我们继续向下走 在 1 2 1 1的基础上 * 我们来到了第三个位置此时我们放入一个面值2的硬币发现此时是用了1个面值1的硬币 和一个面值2的硬币,所以我们总共的总数还是只能有2种 * 1 2 2 1 那么接下来我们来到了4的位置 我们又用了1个 面值2的硬币,那么我们得到 了1 2 2 3 为什么呢 我的位置四就有3种了呢 * 好,让我们来分析分析 第一种那就是全部用面值1的硬币达到了4 第二种是 用面值 1 1 2达到了4 第三种是用了2 2 达到了4 * 由此我们可以用dp[n+1]来存储结果 首先dp[0] = 1; 为什么我的dp[0]要等于1呢,是因为我们第一次使用某一种 * 硬币面值的时候需要在0面值的基础上增1,所以我们的dp[0] = 1就是为我们这样服务的。 那么我们再来解析下dp[]数组的含义 * ,他代表着我们前面使用的所有硬币的数量以及到达n种数 1.【1 1 1 1】 2.【1 2 2 1】 3.【1 2 2 3】 * 1.位置二的1代表我们用了一个面值一的硬币以及我们到达位置2用了两个面值1的硬币 * 2.位置二的2代表了我们在1.的基础上用了面值2的硬币到达了2所以我们此时就有2种方法 下面给出代码 */ //方法一 一维dp int[] coins = { 1, 5, 10, 25 }; int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 0; i < coins.length; i++) { for (int j = coins[i]; j <= n; j++) { dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007; } } return dp[n]; // 方法二 二维的dp // int [][] dp = new int[coins.length+1][n+1]; // for(int i = 1; i <= coins.length; i++) // { // dp[i][0] = 1; // for(int j = 1; j <= n; j++) // { // if(j < coins[i-1]) // dp[i][j] = dp[i-1][j]; // else dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]; // } // } // return dp[coins.length][n]; }
class Coins { public: int mod=1000000007; int countWays(int n) { //假设数的划分严格按照 小的在前 大的在后 //即 1+1+1+1+1+1=0 // 1+5=6 // write code here long long dp_1[100001]={0}; long long dp_5[100001]={0}; long long dp_10[100001]={0}; long long dp_25[100001]={0}; dp_1[0]=1; dp_5[0]=dp_5[5]=1; dp_10[0]=dp_10[10]=1; dp_25[0]=dp_25[25]=1; //分别为 以1结尾的划分方法 以5结尾的划分方法 以10结尾的划分方法 以25结尾的划分方法 for(int i=1;i<=n;i++) // { dp_1[i]=dp_1[i-1]; if(i>5) dp_5[i]=(dp_5[i-5]+dp_1[i-5])%mod;//以5结尾 前面部分可能以5结尾或以1结尾 if(i>10) dp_10[i]=(dp_10[i-10]+dp_5[i-10]+dp_1[i-10])%mod; if(i>25) dp_25[i]=(dp_25[i-25]+dp_10[i-25]+dp_5[i-25]+dp_1[i-25])%mod; } return (dp_1[n]+dp_5[n]+dp_10[n]+dp_25[n])%mod; } };
class Coins { public: int countWays(int n) { memset(dp, 0, sizeof(dp) ); for (int j = 1; j <= n; ++j) { dp[0][j] = 1; } for (int i = 0; i < 4; ++i) { dp[i][0] = 1; } //dp for (int i = 1; i < 4; ++i) { for (int j = 1; j <= n; ++j) { if (j >= coins[i]) { dp[i][j] = (dp[i-1][j] + dp[i][j-coins[i]]) % 1000000007; } else { dp[i][j] = dp[i-1][j] % 1000000007; } } } return dp[3][n]; } private: static const int N = 100003; int dp[4][N] = {0}; const int coins[4] = {1, 5, 10, 25}; };
前面讲的都不够清晰,这里用公式推导表示一下为什么用一维数组
n种硬币凑成sum的方案数,可以假设有i个第n种硬币,然后剩下的则是用n - 1种硬币凑成sum - i * coins[n]的最大方案数,即,经推导可得
所以,代码实现上用一个一维数组去累加即可
class Coins { public: static int countWays(int n) { int coins[] = {1, 5, 10, 25}; // 初始化为1,只有1种硬币时,所有都只有一种方案 vector<int> dp(n + 1, 1); // 从2种硬币开始 for (unsigned int i = 1; i < sizeof(coins) / sizeof(coins[0]); i++) { // dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];,从coins[i]开始,coins[i]以内可coins[i - 1]一致 for (int j = coins[i]; j <= n; j++) { dp[j] += dp[j - coins[i]]; dp[j] %= 1000000007; } } return dp[n]; } };
class Coins { public: int T[3]={25,10,5}; int countWays(int n) { // write code here if(n<=0) return 0; const int M = 1000000007; const int max_size = 100005; vector<vector<int> >dp(max_size,vector<int>(4,0));//dp[i][j]表示只允许使用<T[j]的硬币时,j=0时用全部硬币,j=1时不能用25 //n的表示法==允许使用所有硬币的情况==(n-25)的表示数(即至少使用1个25硬币的情况)+允许使用剩余3种硬币时n的表示法==...== for(int i=0;i<4;i++){ dp[0][i]=1; dp[1][i]=1; } for(int i=2;i<=n;i++){ dp[i][3] = 1; //从5往上考虑所有硬币 for(int k=2;k>=0;k--){ if(i>=T[k]){ dp[i][k] = (dp[i-T[k]][k]+dp[i][k+1])%M;//dp[i-T[k]][k]表示至少使用1个第k种硬币,dp[i][k+1]表示不使用第k种硬币 }else{ dp[i][k] = dp[i][k+1]; } } } return dp[n][0]; } };
class Coins { public: int countWays(int n) { // write code here //动态规划求解 int dp[100005]={0}; dp[0]=1; int coin[4]={1,5,10,25}; for(int i=0;i<4;i++){ for(int j=coin[i];j<=n;j++){ dp[j]=(dp[j]+dp[j-coin[i]])%1000000007;//这句的意思就是旧的通过1,5等旧数据,加上新的数据组合成的一个新的总的数据 } } return dp[n]%1000000007; } };方法二: