Làm thế nào để thực hiện vấn đề đổi xu bằng cách sử dụng phương pháp topDown sử dụng C #?

CoinChangeTopDownApproach nhận 4 tham số, n là số tiền, mảng coin chứa các coin mà từ đó số tiền cần tính, t là tổng số coin, mảng dp sẽ lưu trữ tất cả tiền các giá trị được tính toán. Nếu số tiền là 0 thì trả về 0. Nếu giá trị đã được tính rồi thì trả về từ mảng dp. nếu giá trị không được tính toán thì hãy gọi CoinChangeTopDownApproach một cách đệ quy.

Độ phức tạp về thời gian - O (N)

Độ phức tạp của không gian - O (N)

Ví dụ

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);
}

Đầu ra

3