首页 > 试题广场 >

拼凑钱币

[编程题]拼凑钱币

热度指数：8912 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。

输入描述:

输入包括一个整数n(1 ≤ n ≤ 10000)

输出描述:

输出一个整数,表示不同的组合方案数

示例1

输入

输出

算法知识视频讲解

昵称真难取

//原来的答案 算法复杂度太大 空间复杂度也大
//参考讨论区的 更新 新方法  
import java.util.Scanner;
import java.util.Arrays;
public class Main{
	public static long count(int n){
		if(n <= 0)return 0;
		int[] coins = new int[]{1,5,10,20,50,100};
		long[] dp = new long[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]];//类似斐波那契 后者的种类数基于前者
		}
	}
	return dp[n];
	}
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in); 
		while(sc.hasNext()){
			int n=sc.nextInt();
			long res=count(n);
			System.out.println(res);
		}
	}
}

//原方法 

	import java.util.Scanner;



	import java.util.Arrays;



	public class Main{



	 public static long count(int n){



	    int coins[]={1,5,10,20,50,100};



	    int h=coins.length;



	    long dp[][]=new long[h][n+1];



	    Arrays.fill(dp[0], 1);//基础 该数字都由1组成 方法数是1



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



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



	        int m=j/coins[i];



	        for(int k=0;k<=m;k++){



	        dp[i][j]=dp[i][j]+dp[i-1][j-k*coins[i]];



	         }



	       }



	     }



	return dp[h-1][n];



	}

编辑于 2017-07-18 11:34:50 回复(17)

Picky

#include<iostream>
using namespace std;
 
int main(){
    int N = 0;
    cin >> N;
    long long * F = new long long[N + 1]();
    int c[6] = { 1, 5, 10, 20, 50, 100 };
 
    F[0] = 1;
    for (int i = 0; i < 6; i++)
        for (int v = c[i]; v <= N; v++){
            F[v] = F[v] + F[v - c[i]];
        }
    cout << F[N]<<endl;
    return 0;
}

发表于 2017-07-01 19:17:41 回复(3)

小qaq

http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html

讲的很详细。

发表于 2017-09-14 14:47:19 回复(0)

我的Offer呢！

import java.util.Scanner;

public class Coins {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int amount = sc.nextInt();// 总钱数
            int[] price = { 1, 5, 10, 20, 50, 100 };// 货币面值
            // fun(price, amount);
            fun2(price, amount);
        }
    }
    //方法一:
    public static void fun1(int[] price, int amount) {
        long[][] matrix = new long[price.length][amount + 1];
        for (int i = 0; i < amount + 1; i++) {
            matrix[0][i] = 1;
        }
        for (int i = 0; i < price.length; ++i) {
            matrix[i][0] = 1;
        }
        for (int i = 1; i < price.length; ++i) {
            for (int j = 1; j < amount + 1; ++j) {
                matrix[i][j] += matrix[i - 1][j];
                if (j - price[i] >= 0) {
                    matrix[i][j] += matrix[i][j - price[i]];
                }
            }
        }
        System.out.println(matrix[price.length - 1][amount]);
    }
    //方法二：
    //每一个中间状态只会被用到一次，所以可以重复利用一维数组
    public static void fun2(int[] price, int amount) {
        long[] array = new long[amount + 1];
        for (int i = 0; i < array.length; ++i) {
            array[i] = 1;
        }
        for (int j = 1; j < price.length; ++j) {
            for (int k = 1; k < array.length; ++k) {
                if (k - price[j] >= 0) {
                    array[k] += array[k - price[j]];
                }
            }
        }
        System.out.println(array[amount]);
    }
}

编辑于 2018-03-21 11:19:47 回复(0)

奔跑吧栗子君gogogo

看了大神们的解答才完成的代码

思路：分析问题得递推公式即

使用前i+1种钱币表示总面值为j的方案数=使用前i种钱币表示面值为j的方案数 + 使用前i+1中钱币表示面值为j-coin[i]的方案数

n=int(raw_input())
c=[1,5,10,20,50,100]
methods=[[0 for i in range(n+1)] for j in range(6)]
for i in range(6):
    methods[i][0]=1
for j in range(n+1):
    methods[0][j]=1    
for i in range(1,6):
    for j in range (1,n+1):
        if j>=c[i]:"""这里是指在使用前i种钱币时，只有j>=第i种钱币时，使用前i种钱币找j元钱的方法methods[i][j]才会改变,否则和使用前i-1种钱币组成j元钱的方法相同"""
            methods[i][j]=methods[i-1][j]+methods[i][j-c[i]]
        else:
            methods[i][j]=methods[i-1][j]         
print methods[5][n]

编辑于 2017-09-01 19:40:06 回复(0)

深度学习ing的人


	#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int coin[6]={1,5,10,20,50,100};
    long** dp = new long* [7];
    for(int i=0; i<7; ++i)
        dp[i] = new long[n+1];
    for(int i=0; i<7; ++i)
        dp[i][0] = 1;
    for(int i=0; i<=n; ++i)
        dp[0][i] = 0;
    for(int i=1; i<7; ++i)
    {
        for(int j=1; j<=n; ++j)
        {
            if(j-coin[i-1]>=0)
                dp[i][j] = dp[i-1][j]+dp[i][j-coin[i-1]];
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout<<dp[6][n]<<endl;
    return 0;
}

编辑于 2018-06-13 10:33:46 回复(0)

Python

xiaotan

N=input('')
N=int(N)
penny=[1,5,10,20,50,100]
matrix = [[0 for i in range(6)] for j in range(N+1)]
matrix[0]=[1,1,1,1,1,1]
for i in range(N+1):
    matrix[i][0]=1
    for j in range(1,6):
        if i-penny[j]>0:
            matrix[i][j]=sum(matrix[i-penny[j]][0:j+1])
        if (i-penny[j])==0:
            matrix[i][j]=1
            
print(sum(matrix[i][:]))

发表于 2017-07-06 15:33:37 回复(2)

萧lw

//参照大神：昵称真难区的
//版本：自顶向下的备忘录递归解法

#include <iostream>
 
long count(int type, int money);
 
int price[7] = { 0, 1, 5, 10, 20, 50, 100 };
long amount[7][10000 + 1];
 
int main() {
    for (int i = 0; i <= 10000; i++) {
        amount[1][i] = 1;
    }
    for (int i = 2; i < 7; i++) {
        for (int j = 0; j <= 10000; j++) {
            amount[i][j] = 0;
        }
    }
 
    int n;
    std::cin >> n;
 
    std::cout << count(6, n);
 
    //system("pause");
}
 
long count(int type, int money) {
    if (type == 1) {
        return amount[0][money];
    }
    else {
        for (int i = 0; i <= money / price[type]; i++) {
            int m = money - i*price[type];
            if (amount[type-1][m] != 0) {
                amount[type][money] += amount[type-1][m];
            }
            else {
                amount[type][money] += count(type-1, m);
            }
        }
        return amount[type][money];
    }
}

发表于 2017-07-04 09:06:58 回复(0)

哇咔哇咔

//动态规划，注意用来存储结果的dp必须为8字节长整型，
//在我的windows系统中，long是4字节，long long是8字节；而linux上long就是8字节，
//牛客网判题机应该是linux系统，因此long就可以过，这点要注意一下
#include <iostream>
#include <vector>

using namespace std;

long long coinCombination(int* coins,int kindsOfcoins,int sum)
{
    vector<vector<long long>> dp(kindsOfcoins,vector<long long>(sum+1,0));

    for(int i=0;i<kindsOfcoins;++i)
        dp[i][0]=1;
    for(int i=0;i<=sum;i+=coins[0])
        dp[0][i]=1;
    for(int i=1;i<kindsOfcoins;++i)
    {
        for(int j=1;j<=sum;++j)
        {
            for(int k=0;j-k*coins[i]>=0;++k)
            {
                dp[i][j]+=dp[i-1][j-k*coins[i]];
            }
        }
    }
    return dp[kindsOfcoins-1][sum];
}

int main()
{
    int coins[6]={1,5,10,20,50,100};
    int sum;
    while(cin>>sum)
    {
        long long result=coinCombination(coins,6,sum);
        cout<<result<<endl;
    }
    return 0;
}

编辑于 2017-06-24 19:34:42 回复(0)

pein531

背包问题的变体

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int N = Integer.parseInt(strN);
            System.out.println(solve(N));
        }
    }
    
    private static long solve(int N) {
        if(N == 0) return 0;
        int[] value = {1, 5, 10, 20, 50, 100};
        long[] dp = new long[N + 1];
        Arrays.fill(dp, 1);
        for(int vidx = 1; vidx < 6; vidx++){
            for(int money = 1; money <= N; money++){
                if(money >= value[vidx])
                    dp[money] += dp[money - value[vidx]];
            }
        }
        return dp[N];
    }
}

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

JavaScript

w布响丸辣

var n = parseInt(readline());
    var arr=[1,5,10,20,50,100];
    var dp = [];
    for(var i=0;i<n+1;i++){
        dp[i] = 1;
    }
    for(var i=1;i<arr.length;i++){
        for(var j=arr[i];j<=n;j++){
            dp[j] = dp[j] + dp[j-arr[i]];
        }
    }
    if(n==0)
        print(0)
    else 
        print(dp[n]);

发表于 2018-10-08 17:19:49 回复(0)

小黄豆3

// 动态规划分硬币

#include<iostream>
using namespace std;
long long dp(int n){
    int base[]={1,5,10,20,50,100},m=6;
    long long F[n+1];
    for(int i=0;i<n+1;i++)F[i]=1;
    for(int i=1;i<m;i++){
        for(int j=base[i];j<n+1;j++){
            F[j]=F[j]+F[j-base[i]];
        }
    }
    return F[n];
}
int main() {
    int n;
    while(cin>>n){
        cout<<dp(n)<<endl;
    }
    return 0;
}

编辑于 2017-08-24 16:39:39 回复(0)

Jimmy_gg

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;
    int n;
    while (cin >> n) {
        int arr[] = { 1, 5, 10, 20, 50, 100 };
        int rows = sizeof(arr) / sizeof(arr[0]);
        vector<vector<long long> > dp(rows, vector<long long>(n+1, 0));
        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j <= n; j++) {
                int m = j / arr[i];
                for (int k = 0; k <= m; k++) {
                    dp[i][j] = dp[i][j] + dp[i - 1][j - k * arr[i]];
                }
            }
        }
        cout << dp[rows - 1][n] << endl;
    }
    return 0;
}

参考大神：昵称真难取的程序。

发表于 2017-07-03 20:07:25 回复(0)

天天天天天~~天哪

发表于 2017-07-01 21:11:52 回复(0)

YangWang

发表于 2017-08-29 21:01:16 回复(8)

Java

我讨厌递归算法

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println(getTotal(scanner.nextInt()));
    }


    private static long getTotal(int money) {

        long total = 0L;

        for (int num = 0; num <= money; num += 50) {

            // 求解 100x + 50y = num  非负整数解的个数
            int z1 = (num / 50) / 2 + 1;

            int v20 = (money - num) / 20;

            for (int k = 0; k <= v20; k++) {

                // 求解 10x + 5y <= v1andv5andV10  非负整数解的个数
                int v1andv5andV10 = money - num - 20 * k;

                int tmp = (v1andv5andV10 / 5);
                long kkkk = tmp / 2 + 1;
                long z2 = (tmp + 2-kkkk) * kkkk;

                total = total + z1 * z2;
            }

        }

        return total;
    }
}

不用质疑，这是个正确的答案，也是比较容易理解的答案。内存消耗也应该是最优的，因为没有使用数组。运行速度也应该还可以， money/50 * money/20 次循环运算。

money<= 353583 都能正常运行。

编辑于 2019-07-12 18:02:29 回复(0)

Cyan1956

美团2017 JAVA

[编程题]大富翁游戏
 [编程题]拼凑钱币
 [编程题]最大矩形面积
 [编程题]最长公共连续子串

动态规划求解

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    int M[]={5,10,20,50,100};
    public static void main(String[] args){
        Main s=new Main();
        int n = (new Scanner(System.in)).nextInt();
        long dp[] = new long[n+1];
        Arrays.fill(dp, 1);
        for(int m:s.M){
            for(int j=m;j<=n;j++){
                dp[j]+=dp[j-m];
            }
        }
        System.out.println(dp[n]);
    }
}

发表于 2020-04-19 17:43:28 回复(0)

hs5570

#动态规划：递归式f(n) = f(n)+f(n-coin[j])

import sys
def dp_sol(n):
coin = [1,5,10,20,50,100]
r,c = n+1,len(coin)
dp = [[0 for j in range(c)] for i in range(r)]
for i in range(r): dp[i][0] = 1
for j in range(c): dp[0][j] = 1
for i in range(1,r):
for j in range(1,c):
if i >= coin[j]:
dp[i][j] = dp[i][j-1] + dp[i-coin[j]][j]
else:
dp[i][j] = dp[i][j-1]
return dp[n][c-1]
n = eval(sys.stdin.readline().strip())
ans = dp_sol(n)
print(ans)

发表于 2018-09-20 14:49:20 回复(0)

miaomiaojiang

 Python 
  
   def f(n):  
       if n== 0:  
           return 0  
       a=[1 for i in range(n+1)]  
       p=[1,5,10,20,50,100]  
       for i in range(1,len(p)):  
           for j in range(1,n+1):  
               if j  >= p[i]:  
                   a[j] += a[j-p[i]]  
       return a[n]  
   a=input()  
   print f(a)  

发表于 2018-09-06 17:56:39 回复(0)

华为云招聘2022

可参考leatcode上的解答，用python代码进行实现，原解答链接为：https://leetcode.com/problems/coin-change-2/discuss/99210/python-O(n)-space-dp-solution

# -*- coding:utf8 -*-


def split_money(n):
    money = [1, 5, 10, 20, 50, 100]
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in money:
        for j in range(1, n+1):
           if j >= i: dp[j] += dp[j-i]
    return dp[n]


print(split_money(eval(input())))

编辑于 2018-09-06 15:42:42 回复(0)