IK.AM

@making's tech note


コインの支払い方法

🗃 {Programming/Algorithm/DynamicProgramming/Coin}
🗓 Updated at 2014-03-09T05:59:24Z  🗓 Created at 2014-03-09T05:59:24Z   🌎 English Page

古典的な問題

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

✒️️ Edit  ⏰ History  🗑 Delete