【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d253
【解題想法】DP求硬幣組合數
目錄
Top-down DP (通常比較快)
#include <iostream>
#include <cstring>
using namespace std;
int coins[] = {1, 5, 10, 25, 50};
int dp[5][7500];
int ways(int idx, int money){
if (idx == 5 || money < 0) return 0;
if (money == 0) return 1;
if (dp[idx][money] != -1) return dp[idx][money];
int ret = 0;
for (int i = idx; i < 5; i++){
if (money >= coins[i]){
ret += ways(i, money - coins[i]);
}
}
return dp[idx][money] = ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
memset(dp, -1, sizeof(dp));
while (cin >> n){
cout << ways(0, n) << "\n";
}
return 0;
}
Bottom-up DP
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 7500;
int N = 5; // types of coins
int coin[] = {1, 5, 10, 25, 50};
long long dp[maxn];
int main() {
int n;
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i=0; i<N; i++) {
for (int j=coin[i]; j<maxn; j++) {
dp[j] = dp[j] + dp[j-coin[i]];
}
}
while (cin >> n) {
cout << dp[n] << "\n";
}
return 0;
}
Python code (credit: Amy Chou)
N = [1, 5, 10, 25, 50]
lenN = len(N)
maxn = 7489+5
dp = [0] * maxn
dp[0] = 1
for i in range(lenN):
for j in range(N[i], maxn):
dp[j] += dp[j - N[i]]
while True:
try:
M = int(input())
print(dp[M])
except:
break