多少种分类_

推荐

0pandas0

class Coins {
public:
    int countWays(int n) {
        // write code here
    	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]; 
    }
};

编辑于 2015-08-27 16:57:12 回复(25)

C/C++

周星星_

两种解法

1. 配套书上的递归解法

约定不同硬币凑成的值为n，硬币面值从小到大为[1,5,10,25]

这里逐步分析组成n的过程。

如果放秤砣一样，按照从大到小的顺序，考虑可能存在几个25 =>每种情况下存在几个10 =>每种情况下存在几个5 =>依此类推

代码如下：

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
    }

n为100的时候正确输出242，但是题目数据量到了10w级别运行出现超时。

2. 参考骑着炮弹进城提到的dp方法

这里补充一些解释，如有错漏，还请指正。

我们用dp[i]（i属于1~n ）表示组合成i元一共有几种方法。

首先所有的硬币组合问题都要有基础面值：1元。i的总组合方法一定等于i中最后coin元不用新面值的方法+最后coin元使用新面值的方法。

而最后coin元使用新面值的方法必然等于i-coin的总组合方法。

不用新面值的方法就是旧值

假如只有1元，那对于任给的1~n，必然只有1中组合方法。

假设增加一种新面值：coin元。对于任意i（i属于1~n），

当i<coin的时候，新面值组合方法为0，dp[i]不变。

当i=coin，新组合方法为1，总dp[i]=旧dp[i]+1

当coin<i<2coin，新组合方法仍然为1，总dp[i]=旧dp[i] + 新dp[i-coin]

当i=2coin，仍然有总 dp[i]=旧dp[i] + 新dp[i- coin]

以coin=2为例

同样的道理，题目coin值取值为：[1 5 10 25]，迭代处理即可

代码如下：

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];
    }    
};

编辑于 2016-08-29 11:35:03 回复(7)

Aurora1

    //二维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];
    }

编辑于 2016-09-07 10:00:15 回复(1)

C/C++

nbgao

class Coins {
public:
    int countWays(int n) {
        int a[4] = {1,5,10,25};
        int dp[n+1];
        memset(dp,0,sizeof(dp));
        dp[0] = 1;
        for(int i=0;i<4;i++)
            for(int j=a[i];j<=n;j++)
                dp[j] = (dp[j]+dp[j-a[i]])%1000000007;
        return dp[n];
    }
};

发表于 2019-03-04 02:08:47 回复(0)

Cavs

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;
    }
};

发表于 2017-06-28 19:19:04 回复(0)

Python

Yannyezixin

# -*- 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]

发表于 2016-08-05 17:55:17 回复(0)

木然猫猫

#define N 100010

class Coins {
public:
    int countWays(int n) {
        if(n < 1) return 0;
        int coins[] = {1, 5, 10, 25};
        int dp[N] = {1};
        for(int c : coins){
            for(int i=c; i<=n; ++i){
                dp[i] = (dp[i] + dp[i-c]) % 1000000007;
            }
        }
        return dp[n];
    }
};

运行时间：22ms

占用内存：860k

发表于 2018-12-19 00:32:19 回复(0)

C/C++

oooohhoo

DP递归写法，更容易理解，通过dp数组记录已经计算过的状态防止重复计算，运行时间在2.5s左右未超时，有没有大神对递归写法再做一些优化？

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;
    }
    
};

发表于 2018-09-27 14:16:39 回复(0)

Black_Mamba2

请教各位，我的方法为什么不对
我的思路：这道题目类似上楼梯，斐波那契数列派生出来的问题
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;
        }
    }
}

发表于 2017-07-11 10:11:21 回复(1)

丫头wenj

	/**
	 * 有数量不限的硬币，币值为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;
    }

发表于 2017-07-06 11:06:19 回复(0)

阿狸不是猫

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

发表于 2017-06-29 23:00:55 回复(0)

百乐门前一回首

//都用的动态规划的方法
//详细算法参考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];
    }
}

编辑于 2017-06-29 14:06:50 回复(1)

Java

Sky_廖若星辰

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];
	}

编辑于 2016-10-30 22:25:43 回复(1)

牛客135210号

/*p[i][j]表示用i种硬币构成价值n的方案数

比如p[3][26] = p[2][26] + p[2][16] + p[2][6];

第三种硬币价值为10，分别表示只选择0个，1个，2个10块钱的硬币

*/

class Coins {

public:

int countWays(int n) {

vector<int> vec = {1, 5, 10, 25};

//初始化一个数组p[5][n],p[i][j]表示用i种硬币构成价值n的方案数

int **p = new int*[vec.size() + 1];

for(int i = 0; i <= vec.size(); i++) {

p[i] = new int[n + 1];

//memset(p[i], 0 ,sizeof(int) * (n + 1));

}

//只用一块钱的硬币只有一种方案

for(int i = 1; i <= n; i++) {

p[1][i] = 1;

}

//外层循环表示能够选择的硬币种类

//内层循环表示每个种类的不同值

for(int i = 2; i <= vec.size(); i++) {

for(int j = 1; j <= n; j++) {

int val = j;

int sum = 0;

while(val > 0) {

sum = (sum + p[i - 1][val]) % 1000000007;

val = val - vec[i - 1];

}

p[i][j] = sum;

}

int result = p[4][n];

//for(int i = 0; i < 5; i++) {

// delete[] p[i];

//}

//delete[] p;

return result;

}

};

发表于 2016-03-31 10:24:15 回复(0)

Python

BiangTiu

def countWays(self, n):
    if n < 1:
        return 0
    dp = [0] * (n+1)
    state = [1, 5, 10, 25]
    dp[0] = 1
    for s in state:
        for i in range(s, n+1):
            dp[i] = (dp[i] + dp[i-s]) % 1000000007
    return dp[n]

发表于 2021-10-14 20:24:42 回复(0)

一只老风铃

提供一种笨方法：分类讨论

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;
    }
};

发表于 2021-06-18 11:20:59 回复(0)

TankWitch

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};
};

发表于 2020-07-19 08:00:30 回复(0)

nowcoder_wyb

前面讲的都不够清晰，这里用公式推导表示一下为什么用一维数组
n种硬币凑成sum的方案数，可以假设有i个第n种硬币，然后剩下的则是用n - 1种硬币凑成sum - i * coins[n]的最大方案数，即 $dp[n][sum] = \sum_{i = 0}^{sum / coins[n]}dp[n - 1][sum - i * coins[n]]$ ，经推导可得

$\begin{aligned} dp[n][sum] &= dp[n - 1][sum - 0 * coins[n]] + dp[n - 1][sum - 1 * coins[n]] +...+ dp[n - 1][sum - sum / coins[n] * coins[n]] \\ & = \sum_{i = 0}^{sum / coins[n]}dp[n - 1][sum - i * coins[n]] \\ & = dp[n - 1][sum] + \underbrace{\sum_{i = 1}^{sum / coins[n]}dp[n - 1][sum - i * coins[n]]}_{令sum1 = sum - coins[n]} \\ & = dp[n - 1][sum] + \sum_{i = 1}^{sum1 / coins[n] + 1}dp[n - 1][sum1 - (i - 1) * coins[n]] \\ & = dp[n - 1][sum] + \underbrace{\sum_{i = 0}^{sum1 / coins[n]}dp[n - 1][sum1 - i * coins[n]]}_{dp[n][sum1]} \\ & = dp[n - 1][sum] + dp[n][sum - coins[n]] \end{aligned}$

所以 $dp[n][sum] = dp[n - 1][sum] + dp[n][sum - 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];
        }
    };

发表于 2020-04-26 11:21:21 回复(0)

C/C++

Shopee内推小虾米

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];
    }
};

发表于 2020-02-10 19:16:17 回复(0)

C/C++

kevindebury

方法一：动态规划求解：

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;
    }
};

方法二：

使用递归求解但是递归会出现非常多的无用步骤，所以需要进行优化。。。

编辑于 2020-02-05 17:14:56 回复(0)

Dxoca

我博客真理的很齐全 https://dxoca.cn/Algorithm/206.html

发表于 2019-08-08 14:08:59 回复(0)

多少种分类

问题信息

热门推荐

通过挑战的用户

相关试题