C＃を使用したtopDownアプローチを使用してコイン交換問題を実装するにはどうすればよいですか？

CoinChangeTopDownApproachは4つのパラメーターを取ります、nは金額、coins配列には金額を計算する必要のあるコインが含まれ、tはコインの総数、dp配列はすべてのpreを格納します計算値。金額が0の場合は、0を返します。値がすでに計算されている場合は、dp配列から返します。値が計算されない場合は、CoinChangeTopDownApproachを再帰的に呼び出します。

時間計算量 − 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