如何使用 C# 使用 topDown 方法实现硬币找零问题？

CoinChangeTopDownApproach 有 4 个参数，n 是数量，coins 数组包含需要计算数量的硬币，t 是硬币总数，dp 数组将存储所有预先计算的值。如果金额为 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