題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b029。
此題用 Dynamic Programming,和 b028: 忙碌的超商店員很接近。
主要的想法為:目前的組合種類數等於 目前面額減去各硬幣面額之組合種類數的加總。
程式碼:
- #include <iostream>
- #include <cstring>
- using namespace std;
- int main()
- {
- int cVal[5] = {2, 5, 10, 20, 25};
- int cnt[1001];
- // 將所需組合種類數全部設為 0
- memset(cnt, 0, sizeof(cnt));
- cnt[0] = 1;
- int n;
- cin >> n;
- for(int i = 0; i < 5; i++)
- {
- for(int j = cVal[i]; j <= n; j++)
- {
- // 目前的組合種類數等於 目前面額減去各硬幣面額之組合種類數的加總
- cnt[j] += cnt[j - cVal[i]];
- }
- }
- cout << cnt[n] << endl;
- return 0;
- }
沒有留言:
張貼留言