andy6804tw
8/5/2016 - 5:01 AM

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23650 這題利用動態規劃先把1~15000的換錢方法存入陣列(long) coins[ ]={1,5,10,20,50} 1.首先建立dp[1500

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23650

這題利用動態規劃先把1~15000的換錢方法存入陣列(long) coins[ ]={1,5,10,20,50} 1.首先建立dp[15001]個陣列並每個存1(一元的分法) 2.外迴圈從coin[i=1]開始coin[4]內迴圈從j=coin[i]開始15000,dp[ j ]+=dp[ j-coins[i] ] ex:10元 i=1時 dp[10]+=dp[10-5]=1+2=3 i=2時 dp[10]+=dp[10-10]=3+1=4

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		long dp[] = new long[15001];
		int coins[] = { 1, 5, 10, 20, 50 };
		for (int j = 0; j <= 15000; j++)
			dp[j] = 1;
		for (int i = 1; i < 5; i++) {
			for (int j = coins[i]; j <= 15000; j++) {
				dp[j] += dp[j - coins[i]];
			}
		}
		int n = scn.nextInt();
		while (n-- != 0) {
			int num = scn.nextInt();
			System.out.println(dp[num]);
		}
	}
	/* 
    題目:2015 闖關組 [Problem B5-中易] Coin Change(換零錢方法數)
    作者:1010
    時間:西元 2016 年 8 月 */
}