メモ化再帰。
1 #include <iostream>
2 #include <cstring>
3
4 using namespace std;
5
6 int v[8] = {200, 100, 50, 20, 10, 5, 2, 1};
7
8 int dp[8][201];
9 int dfs(int index, int rem) {
10 if (index == 8) {
11 if (rem == 0) return 1;
12 return 0;
13 }
14 if (dp[index][rem] >= 0) return dp[index][rem];
15 int sum = 0;
16 for (int i = 0; i <= rem; i += v[index]) {
17 sum += dfs(index+1, rem - i);
18 }
19 return dp[index][rem] = sum;
20 }
21
22 int main() {
23 memset(dp, -1, sizeof(dp));
24 cout << dfs(0, 200) << endl;
25 return 0;
26 }