C#でボトムアップアプローチを使ってコイン両替問題を実装する方法

コイン両替問題とは

コイン両替問題は、指定された金額を、使用できるコインの種類だけで「最小枚数」で支払う方法を求める、動的計画法の代表的な応用例です。貪欲法（常に一番額面の大きいコインから選ぶ方法）では最適解が得られないコイン体系（例：{1, 7, 10}）でも、動的計画法を使えば確実に最小枚数を求められます。

ボトムアップアプローチの考え方

ボトムアップアプローチ（タブレーション）では、金額0のような小さな部分問題から順に解き、その結果を配列に記録しながら目的の金額へと積み上げていきます。トップダウン方式（メモ化再帰）と違い、再帰呼び出しが不要なためスタックオーバーフローを気にせずに済むのが大きな利点です。

CoinChangeBottomUpApproach メソッドは、次の3つのパラメータを受け取ります。

• n： 支払うべき金額
• coins： 使用可能なコインの額面を格納した配列
• t： コインの種類数（配列の要素数）

処理の流れは以下のとおりです。

1. これまでに計算した値を保持するためのDP配列（dp）を宣言します。dp[i] には「金額iを支払うのに必要な最小コイン枚数」が格納されます。
2. 金額1からnまで順番にループし、各金額についてすべてのコインを試しながら最小枚数を計算します。
3. 「現在の金額 − コインの額面」という部分問題の解がすでにdp配列に保存されていれば、それを再利用して重複計算を回避します。
4. 最終的に dp[n] の値が答えとなります。

計算量

• 時間計算量： O(N)（厳密にはコインの種類数Tを掛けた O(N×T)。Tを定数とみなせば O(N)）
• 空間計算量： O(N)（DP配列の分だけメモリを使用）

実装例（C#）

using System;

public class DynamicProgramming {
    // dp[i] = 金額iを支払うのに必要な最小コイン枚数
    public int CoinChangeBottomUpApproach(int n, int[] coins, int t) {
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = int.MaxValue;
            for (int j = 0; j < t; j++) {
                // コインcoins[j]が使用可能で、残り金額の解が計算済みの場合
                if (i - coins[j] >= 0 && dp[i - coins[j]] != int.MaxValue) {
                    int subProb = dp[i - coins[j]];
                    dp[i] = Math.Min(dp[i], subProb + 1);
                }
            }
        }
        return dp[n];
    }
}

public class Program {
    static void Main(string[] args) {
        DynamicProgramming dp = new DynamicProgramming();
        int[] coins = { 1, 7, 10 };
        int ss = dp.CoinChangeBottomUpApproach(15, coins, coins.Length);
        Console.WriteLine(ss);
    }
}

出力結果

3

実行結果の解説

この例では、金額15をコイン {1, 7, 10} で支払うケースを扱っています。最適な組み合わせは「7 + 7 + 1」の3枚であり、プログラムも正しく3を出力します。

もし貪欲法で「10 + 1×5」と選んでしまうと6枚必要となり、最適解になりません。この比較からも、動的計画法によって全パターンを網羅的に評価することの有効性がわかります。

まとめ

ボトムアップアプローチでは、小さな金額から順に最小コイン枚数を表に埋めていくことで、重複計算を排除し、効率的に答えを求められます。コイン両替問題は動的計画法の入門に最適な題材なので、ぜひ別のコイン体系や金額でも試してみてください。