Cách triển khai bài toán đổi tiền (Coin Change) bằng phương pháp Top-Down trong C#

Phương pháp CoinChangeTopDownApproach nhận 4 tham số: n là số tiền, mảng coins chứa các mệnh giá, t tổng số mệnh giá, mảng dp lưu các giá trị đã tính. Nếu n == 0 trả về 0. Nếu giá trị đã tính thì trả về từ dp. Nếu chưa tính thì gọi đệ quy CoinChangeTopDownApproach.

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

Độ phức tạp 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.Length;
    int res = dp.CoinChangeTopDownApproach(15, coins, t, dp1);
    Console.WriteLine(res); // Output: 3
}

Kết quả đầu ra

3