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

CoinChangeBottomUpApproach는 3개의 매개변수를 취합니다. 입력 n은 금액이고, coin 배열은 총 동전 수를 포함하고, t는 총 동전 수를 포함합니다. 이전에 계산된 값을 저장하는 동적 배열을 선언합니다. 배열을 반복하고 금액을 계산하는 데 필요한 최소 동전을 계산합니다. 계산이 이미 완료된 경우 동적 배열에서 값을 가져옵니다.

시간 복잡도 − 오(N)

공간 복잡성 − 오(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