C#을 사용하여 하향식 접근 방식을 사용하여 동전 변경 문제를 구현하는 방법은 무엇입니까?

CoinChangeTopDownApproach는 4개의 매개변수를 사용하고, n은 금액이고, 동전 배열은 금액을 계산해야 하는 동전을 포함하고, 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