首页 > 试题广场 >

换零钱

[编程题]换零钱

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

考虑仅用1分、5分、10分、25分和50分这5种硬币支付某一个给定的金额。例如需要支付11分钱，有一个1分和一个10分、一个1分和两个5分、六个1分和一个5分、十一个1分这4种方式。
请写一个程序，计算一个给定的金额有几种支付方式。
注：假定支付0元有1种方式。

输入描述:

输入包含多组数据。

每组数据包含一个正整数n（1≤n≤10000），即需要支付的金额。

输出描述:

对应每一组数据，输出一个正整数，表示替换方式的种数。

示例1

输入

11
26

输出

4
13

算法知识视频讲解

Java

安徒生的谎言

// write your code here
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int m=sc.nextInt();
            int[] v= {1,5,10,25,50};
            long[] dp=new long[m+1];
            dp[0]=1;
            for(int i=0;i<v.length;i++) {
                for(int j=1;j<=m;j++) {
                    if(j>=v[i]) {
                        dp[j]+=dp[j-v[i]];
                    }
                }
            }
            System.out.println(dp[m]);
        }
    }
}

发表于 2018-01-26 15:25:37 回复(0)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] money = {1, 5, 10, 25, 50};
		while (sc.hasNext()) {
			int n = sc.nextInt();
			long[] dp = new long[n + 1];
			dp[0] = 1;
			for (int i = 0; i < money.length; i ++ ) {
				for (int j = money[i]; j < dp.length; j ++ ) {
					dp[j] += dp[j - money[i]];
				}
			}
			System.out.println(dp[n]);
		}
	}
}

发表于 2016-10-14 00:25:15 回复(0)