alan23273850 的刷題筆記
d253: 00674 - Coin Change
Tags: coin-change
出處：https://zerojudge.tw/ShowProblem?problemid=d253
提交：https://zerojudge.tw/Submissions?problemid=d253&account=allllllan123456
問題：給定一個非負整數 $n\in[0,7489]$，問你方程組 1A + 5B + 10C + 25D + 50E = $n$ 有多少組非負整數解。
解法：此乃 coin change 問題，可參閱本站對於該問題的解析。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int price[] = {1,5,10,25,50};
6 int n, DP[7490]={1}; // important initial condition
7 for (int i=0; i<sizeof(price) / sizeof(price[0]); i++)
8 for (int j=price[i]; j<=7489; j++)
9 DP[j] += DP[j-price[i]];
10 while (cin >> n) cout << DP[n] << '\n';
11 return 0;
12}