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

Phương pháp CoinChangeBottomUpApproach nhận 3 tham số: n là số tiền cần đổi, mảng coins chứa các mệnh giá tiền, t là tổng số mệnh giá. Khai báo mảng động dp lưu các giá trị đã tính toán trước. Duyệt qua mảng và tính số đồng tiền tối thiểu để đạt số tiền. Nếu đã tính toán thì lấy giá trị từ mảng dp.

Độ 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 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.Length);
    Console.WriteLine(ss); // Output: 3
}

Kết quả đầu ra

3

Lưu ý: Code gốc có một số lỗi nhỏ (như coins.Count() thay vì coins.Length, và logic trả về dp[n]+1 có thể cần xem lại). Phiên bản trên đã được sửa để chạy đúng.