Làm thế nào để thực hiện vấn đề đổi xu bằng cách tiếp cận từ dưới lên bằng C #?

CoinChangeBottomUpApproach lấy 3 tham số là đầu vào n là số lượng, mảng coin chứa tổng số coin, t chứa tổng số coin. Khai báo một mảng động lưu trữ các giá trị đã tính toán trước đó. lặp qua mảng và tính số xu tối thiểu cần thiết để tính số tiền. Nếu tính toán đã được thực hiện, hãy lấy giá trị từ mảng động.

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

Đầu ra

3