---
title: コインの支払い方法
tags: []
categories: ["Programming", "Algorithm", "DynamicProgramming", "Coin"]
date: 2014-03-09T05:59:24Z
updated: 2014-03-09T05:59:24Z
---

古典的な問題

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