古典的な問題
25セント、10セント、5セント、1セントを使ってnセントを支払う方法は何通りあるでしょうか?
public class Coin {
static long[] memo = new long[10000];
static long countWays(int n, int max) {
if (n < 0) return 0;
if (n == 0) return 1;
if (memo[n] > 0) return memo[n];
long ways = 0;
if (max >= 25) {
ways += countWays(n - 25, 25);
}
if (max >= 10) {
ways += countWays(n - 10, 10);
}
if (max >= 5) {
ways += countWays(n - 5, 5);
}
if (max >= 1) {
ways += countWays(n - 1, 1);
}
return ways;
}
public static void main(String[] args) {
for (int i = 1; i <= 100; i++) {
System.out.println(i + " = " + countWays(i, 25) + " ways");
}
}
}
実行結果
1 cent => 1 ways
2 cent => 1 ways
3 cent => 1 ways
4 cent => 1 ways
5 cent => 2 ways
6 cent => 2 ways
7 cent => 2 ways
8 cent => 2 ways
9 cent => 2 ways
10 cent => 4 ways
11 cent => 4 ways
12 cent => 4 ways
13 cent => 4 ways
14 cent => 4 ways
15 cent => 6 ways
16 cent => 6 ways
17 cent => 6 ways
18 cent => 6 ways
19 cent => 6 ways
20 cent => 9 ways
21 cent => 9 ways
22 cent => 9 ways
23 cent => 9 ways
24 cent => 9 ways
25 cent => 13 ways
26 cent => 13 ways
27 cent => 13 ways
28 cent => 13 ways
29 cent => 13 ways
30 cent => 18 ways
31 cent => 18 ways
32 cent => 18 ways
33 cent => 18 ways
34 cent => 18 ways
35 cent => 24 ways
36 cent => 24 ways
37 cent => 24 ways
38 cent => 24 ways
39 cent => 24 ways
40 cent => 31 ways
41 cent => 31 ways
42 cent => 31 ways
43 cent => 31 ways
44 cent => 31 ways
45 cent => 39 ways
46 cent => 39 ways
47 cent => 39 ways
48 cent => 39 ways
49 cent => 39 ways
50 cent => 49 ways
51 cent => 49 ways
52 cent => 49 ways
53 cent => 49 ways
54 cent => 49 ways
55 cent => 60 ways
56 cent => 60 ways
57 cent => 60 ways
58 cent => 60 ways
59 cent => 60 ways
60 cent => 73 ways
61 cent => 73 ways
62 cent => 73 ways
63 cent => 73 ways
64 cent => 73 ways
65 cent => 87 ways
66 cent => 87 ways
67 cent => 87 ways
68 cent => 87 ways
69 cent => 87 ways
70 cent => 103 ways
71 cent => 103 ways
72 cent => 103 ways
73 cent => 103 ways
74 cent => 103 ways
75 cent => 121 ways
76 cent => 121 ways
77 cent => 121 ways
78 cent => 121 ways
79 cent => 121 ways
80 cent => 141 ways
81 cent => 141 ways
82 cent => 141 ways
83 cent => 141 ways
84 cent => 141 ways
85 cent => 163 ways
86 cent => 163 ways
87 cent => 163 ways
88 cent => 163 ways
89 cent => 163 ways
90 cent => 187 ways
91 cent => 187 ways
92 cent => 187 ways
93 cent => 187 ways
94 cent => 187 ways
95 cent => 213 ways
96 cent => 213 ways
97 cent => 213 ways
98 cent => 213 ways
99 cent => 213 ways
100 cent => 242 ways