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

コイン両替問題とは

コイン両替問題は、指定された金額を最小枚数のコインで作るという古典的な動的計画法（DP）の問題です。本記事では、C#を用いて「トップダウンアプローチ（メモ化再帰）」でこの問題を解く方法を解説します。

アルゴリズムの基本構造

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

• n：作りたい金額
• coins：使用できるコインの種類を格納した配列
• t：コインの総数
• dp：計算済みの値をキャッシュするための配列

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

1. 金額が0なら0を返します（これ以上コインは不要なため）。
2. dp配列に既に計算済みの値があれば、それをそのまま返し、無駄な再計算を防ぎます。
3. まだ計算されていない場合は、各コインを使った部分問題を再帰的に呼び出し、得られた結果の最小値に1を加えて答えとし、dp配列に保存してから返します。

計算量

• 時間計算量：O(N)
• 空間計算量：O(N)

実装例

public class DynamicProgramming{    public int CoinChangeTopDownApproach(int n,int[] coins,int t,int[] dp){      if (n == 0){        return 0;      }      if (dp[n] != 0){        return dp[n];      }      int ans = int.MaxValue;      for (int i = 0; i < t; i++){        if (n - coins[i] >= 0){          int subprob = CoinChangeTopDownApproach(n - coins[i], coins, t, dp);          ans = Math.Min(ans, subprob + 1);        }   }    dp[n] = ans;   return dp[n];   }}static void Main(string[] args){    DynamicProgramming dp = new DynamicProgramming();    int N = 15;    int[] coins = { 1, 7, 10 };    int[] dp1 = new int[100];    int t = coins.Count();    int res = dp.CoinChangeTopDownApproach(15, coins, t, dp1);    Console.WriteLine(res);}

出力結果

3

実行結果の解説

この例では、金額15をコイン {1, 7, 10} で作ることを考えます。「7 + 7 + 1」のように7円玉を2枚と1円玉を1枚使えば、合計3枚で金額15を作れます。他の組み合わせ（例：10 + 1×5）よりも少ない枚数であるため、プログラムは最小枚数である「3」を出力します。

トップダウンアプローチでは、一度計算した金額に対する答えをdp配列に記録するため、同じ部分問題を何度も計算することがなくなり、素朴な再帰に比べて大幅に効率が向上します。