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

CoinChangeBottomUpApproachは、入力nが金額、coins配列にコインの総数、tにコインの総数が含まれるため、3つのパラメーターを取ります。以前に計算された値を格納する動的配列を宣言します。配列をループして、金額を計算するために必要な最小コインを計算します。計算がすでに行われている場合は、動的配列から値を取得します。

時間計算量- O（N）

スペースの複雑さ- O（N）

例

public class DynamicProgramming{
   public int CoinChangeBottomUpApproach(int n,int[] coins,int t){
      int[] dp = new int[100];
      for (int i = 1; i < n; i++){
         dp[i] = int.MaxValue;
         for (int j = 0; j < t; j++){
            if (i - coins[j] >= 0){
               int subProb = dp[i - coins[j]];
               dp[i] = Math.Min(dp[i], subProb + 1);
            }
         }
      }
      return dp[n]+1;
   }
}

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

出力

3