UVa 00674 題解 — C++

教大家一個辨別要用貪心法還是動態規劃的方法： 當你遇到求最小問題的時候： 1. 面額全部具備倍數關係：貪心法 2. 面額不具備倍數關係：動態規劃 當你遇到求方法數的時候，要用動態規劃去做。 好現在回來這一題，這一題我們可以只用一維的陣列做動態規劃，但前提是小的要先做。 這邊要注意付 0 我們是 1 種方法 (什麼都不付)。 一開始因為 1 塊錢在付任何金額的情況下都只有一種方法，先初始化付 i 塊錢的方法數 dp[i] = 1, $1 \le i \le 10000$。 接著我們可以看新增不同面額 dollar[i] 後，方法數 dp[j] 的變化就是 dp[j] += dp[j-dollar[i]]。 舉例而言： 當我們要付 10 塊 (dp[10]) 的時候，用 1 塊錢付的方法就是 1 種，目前 dp[10] 是 1。 現在看新增 5 塊面額的時候，付 10 塊的方法就會變成 dp[10] + dp[10-5]，因為這題目可以拆成： 1. 原本的 dp[10] 是用 1 塊錢的方法 2. dp[5] = dp[10-5] 是先用了一個 5 塊錢之後，剩下 5 塊錢怎麼用的方法。 因為我們會從小到大維護這個陣列，所以 dp[5] 已經被維護過，他是 dp[5] + dp[0] = 2 種方法： 1. 原本的 dp[5] 是用 1 塊錢的方法 2. dp[0] = dp[5-0] 是先用了一個 5 塊錢之後，剩下 0 塊錢怎麼用的方法，顯然是 1 種。 所以 dp[5] 已經是 2，現在的 dp[10] = dp[10] + dp[10-5] = 1 + 2 = 3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int coin;
	int dollar[4]={5, 10, 25, 50}, dp[10000];
	
	for (i=0;i<=10000;i++)  // 使用一塊錢 
		dp[i] = 1;
		
	for (i=0;i<4;i++) {
		for (j=1;j<=10000;j++) {
			if (j >= dollar[i]) {  // 可用 dollar[i] 面額 
				dp[j] += dp[j-dollar[i]];
			}
		}
	}
	
	while (cin >> coin) {
		cout << dp[coin] << endl;
	}

	return 0;
}