首页 > 试题广场 >

硬币划分

[编程题]硬币划分
  • 热度指数：2058 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？

输入描述:
输入整数n.(1<=n<=100000)


输出描述:
输出组合数，答案对1e9+7取模。
示例1

输入

13

输出

16
算法知识视频讲解
添加回答
执着在一线头像 执着在一线 
# python3
def change(coins, n):
    len1 = len(coins)
    if len1 == 0 and n < 1 or n > 100000:
        return None
    ways = [0] * (n + 1)  # 初始化
    ways[0] = 1
    for i in range(len1):
        for j in range(coins[i], n + 1):
            # 保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007
            ways[j] = (ways[j] + ways[j - coins[i]]) % 1000000007
    print(ways[n])
 
if __name__ == '__main__':
    coins, n = [1, 2, 5, 10], int(input())
    change(coins, n)

发表于 2019-09-02 21:04:01 回复(2)
卷毛侠头像 卷毛侠
#include<iostream>
using namespace std;

int countWays(int n) {
        // write code here
        int coins[4]={1,2,5,10};
        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];
    }
int main()
{
    int n;
    cin>>n;
    cout<<countWays(n)<<endl;
}

发表于 2019-11-05 19:45:59 回复(0)
skikda头像 skikda
#include<iostream>
using namespace std;
int a[4] = { 1,2,5,10 };
int cnt = 0;
int num;
int total = 0;
long long dp[1000001] = {1};
void dfs(int n) {
if (total == num) {
cnt++;
cnt = cnt % (int(1e9 + 7));
return;
}
if (total > num)return;
for (int i = n; i < 4; i++) {
total += a[i];
dfs(i);
total -= a[i];
}
}
void dd(int n) {
for (int i = 0; i < 4; i++) {
for (int j =a[i]; j <=n; j++) {
dp[j] = (dp[j]+dp[j-a[i]]) % 1000000007;
}
}

}
int main() {
cin >> num;
dd(num);
cout << dp[num];
return 0;
}



编辑于 2019-09-21 21:46:58 回复(0)
Python
0b100001101000头像 0b100001101000 
n = int(input())
m = [1] + [0]*n
for i in (1,2,5,10):
    for j in range(i,n+1):
        m[j] = (m[j] + m[j-i]) % 1000000007
print(m[-1])


发表于 2019-09-17 01:11:20 回复(0)
Python
elij头像 elij 
def calc(n):
    n = int(n)
    coins = [1, 2, 5, 10]
    
    memo = [0] * (n + 1)
    memo[0] = 1
    
    for i in coins:
        for j in range(i, n+1):
            # 必须与此数取模而非题目给的 1e9+7
            memo[j] = (memo[j] + memo[j-i]) % 1000000007

    return memo[n] 
    
print(calc(input()))

编辑于 2019-10-26 00:38:02 回复(0)
文子杰头像 文子杰
//C语言编程，使用动态规划，已经通过测试
#include <stdio.h>
#include <string.h>

int coins[4]={1,2,5,10};
long sum=0;

void Div(long n,int m)
{
    if(m>2)
    {

        int k=n/coins[m-1],i;
        for(i=0;i<=k;i++)
        {
            Div(n-i*coins[m-1],m-1);
        }

    }
    else if(m==2)
    {
        sum=(sum+n/2+1)%(1000000007);
       // printf("%ld\n",sum);
    }

}


int main()
{

    long n;
    scanf("%ld",&n);
    Div(n,4);
    printf("%ld\n",sum);


    return 0;
}
发表于 2019-09-22 22:26:43 回复(0)
羡鱼201907071247985头像 羡鱼201907071247985
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
    Scanner input=new Scanner(System.in);
    int n=input.nextInt();
    int coins[]= {1,2,5,10};
    int [] dp=new int[100001];
    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;
        }
    }
    System.out.println(dp[n]);
    
    }
}
发表于 2019-09-03 16:09:27 回复(4)
Java
来学习的小张头像 来学习的小张
状态F(i,j) :前i种硬币组成j的方法个数
转移方程：F(i,j): F(i - 1,j) + F(i,j - coins[i - 1]);
初始状态：F(i,0) = 1;  F(0,j) = 0;
返回：F(coins,size(),n) 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = {1,2,5,10};
        int[][] methodNum = new int[arr.length + 1][n + 1];
        for(int i = 0;i <= arr.length;i++){
            methodNum[i][0] = 1;
        }
        for(int i = 1;i <= arr.length;i++){
            for(int j = 0;j <= n;j++){
                if(j >= arr[i - 1]){
                    methodNum[i][j] = (methodNum[i - 1][j] + methodNum[i][j - arr[i - 1]]) % 1000000007;
                }else{
                     methodNum[i][j] = methodNum[i - 1][j];
                }
            }
        }
        System.out.println(methodNum[arr.length][n]);
    }
}

发表于 2022-04-08 15:48:58 回复(0)
Orange1ce头像 Orange1ce 
# i->硬币金额
# j->硬币编号
# dp[i] += dp[i-coin[j]]
n = input()
n = int(n)
coins = [1, 2, 5, 10]
dp = [0]*(n+1)
dp[0] = 1
for j in range(len(coins)):
    # 循环的起点coins[j]，从本轮选择的硬币面额开始循环
    for i in range(coins[j], n+1):
        dp[i] += dp[i-coins[j]]
print(dp[-1]%(10**9+7))

发表于 2021-07-25 23:07:17 回复(0)
燃尽之白丶头像 燃尽之白丶 
var waysToChange = function(n) {
   let arr = []
   let arrs = [1,2,5,10]
   arr[0] = 1
   for(let i = 0;i<arrs.length;i++){
      for(let j = arrs[i];j<n+1;j++){
          arr[j] ? arr[j] = arr[j] :arr[j] = 0
         arr[j] = arr[j] + arr[j - arrs[i]]
      }
   }
return arr[arr.length - 1]
};


发表于 2020-11-09 11:12:20 回复(0)
Python
xiaoghggghgg头像 xiaoghggghgg 


n = int(input())
n_5 = n//5
idea = 0
for x in range(n_5+1):
    idea += (x//2+1)*((n-5*x)//2+1)
print(int(idea%(1e9+7)))


 运行时间： 46 ms 占用内存：3556K
编辑于 2019-09-28 22:30:59 回复(0)
有些音乐适合某些环境头像 有些音乐适合某些环境
暴力破解
public static void combine(int k)
    {
        if(k<=0)
            return;
        int sum=0,i=0,j=0,m=0,n=0,num=0;
        for(i=0;i<=k/10;i++)
        {
            for(j=0;j<=(k-i*10)/5;j++)
            {
                for(m=0;m<=(k-i*10-j*5)/2;m++)
                {
                    for(n=0;n<=(k-i*10-j*5-m*2);n++)
                    {              
                        if(k==10*i+5*j+2*m+n)
                            num++;
                    }
                }
            }
        }
        num=(int) (num%(1e9+7));
        System.out.println(num);
    }


发表于 2019-09-26 15:30:42 回复(0)
onone头像 onone 
function dealData(n){
    var dp=new Array(100001);
    for(var k=0;k<dp.length;k++){
        dp[k]=0;
    }
    dp[0]=1;
    var coins=[1,2,5,10];
    for(var i=0;i<coins.length;i++){
        for(var j=coins[i];j<dp.length;j++){
            dp[j]=(dp[j]+dp[j-coins[i]])%1000000007
        }
    }
    print(dp[n]);
}
dealData(readline());
为什么在牛客网的编译器上，数组设为n+1不能通过？
发表于 2019-09-22 20:49:39 回复(0)
Python
龙江头像 龙江
#请帮忙看看哪里有问题，部分通过，大数不行
#枚举，从大到小，依次枚举计数
n = int(input(''))
list1=0
for i in range(0,(n//10)+1):
    shi = 10*i
    for j in range(0,((n-shi)//5)+1):
        wu = 5*j
        list1=list1+((n-shi-wu)//2)+1
print(list1)
编辑于 2019-09-12 22:25:21 回复(1)
C/C++
快乐的民工头像 快乐的民工 
#include<stdio.h>
#include<math.h>
int main() {
	long long n;
	long long coins[] = {1,2,5,10};
		long long dp[1000001];
	long long i, j;
	dp[0] = 1;
	scanf("%lld", &n);
	for (i = 0; i < 4; i++) {
		for (j = coins[i]; j <= n; j++) {
			dp[j] = (dp[j] + dp[j - coins[i]])%1000000007;
		}
	}
	printf("%lld", dp[n]);
	return 0;
}

令f（0） = 1    f(1) = f(1)+f(1-1)     f(2) = f(2)+f(2-2)+f(2-1)  f(3) = f(3)+f(3-2)+f(3-1)   定义一个数据保存a[1] 表示组成1分钱的种数    a[n] 表示组成n分钱的种数
抄那个java大佬的思路，不会写，只能硬背
发表于 2019-09-09 22:28:02 回复(4)
good_boy头像 good_boy
package Arithmetic;

public class charge_coins2 {
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //具有的零钱的面值
        double[] V = new double[]{1,0.5,0.1,0.05,0.02,0.01};
        //需要找的零钱
        double money = 1.23;
        //返回结果的数组
        int [] result = new int[V.length];
        result = Greedy(V, money);
        for (int i=0;i<result.length;i++){
            System.out.println("  "+result[i]);
        }
    }
    
    static int[] Greedy(double[] V, double money){
        //返回结果的数组
        int [] result = new int[V.length];
        //先对数据进行挑选，先将零钱中面值大于要找的零钱进行剔除
        int j=0;
        //将挑选的数值进行贪婪最优化
        for (int i=0; i<V.length;++i){
            //向下取整
            if (money>=V[i]){
                int number=(int)Math.floor((money*100)/(V[i]*100));
                if(money-number*V[i]==0){
                    result[j]=number;
                    ++j;
                    break;
                }else{
                    //出现数据泄露，最后money=0.00999999999988
                    money=money-number*V[i];
                    result[j]=number;
                    ++j;
                }
            }else{
                result[j]=0;
                ++j;
            }
        }
        //进行结果反向验证
        double sum=0;
        for(int i=0; i<V.length;i++){
            sum=sum+result[i]*V[i];
        }
        if (sum!=money){
            result[result.length-1]+=1;
        }
        return result;
    }
}

发表于 2019-09-07 21:07:04 回复(1)
无言201810231837228头像 无言201810231837228 
def change(coins, n):
    len1 = len(coins)
    if len1 == 0 and n < 1 or n > 100000:
        return None
    ways = [0] * (n + 1)  # 初始化
    ways[0] = 1
    for i in range(len1):
        for j in range(coins[i], n + 1):
            # 保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007
            ways[j] = (ways[j] + ways[j - coins[i]]) % 1000000007
    print(ways[n])
if __name__ == '__main__':
    coins, n = [1, 2, 5, 10], int(input())
    change(coins, n)



发表于 2019-09-05 16:08:58 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 瓜子二手车 2019 大数据开发工程师 Java工程师
上传者：小小
难度：
17条回答 11223浏览

热门推荐

通过挑战的用户

相关试题

硬币划分

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号