Mô phỏng thuật toán Đổi tiền (ít xu nhất)

Coin Change · Nhóm: Quy hoạch động

Đổi tiền (ít xu nhất) (Coin Change), nhóm Quy hoạch động.

Mã Python

def coin_change(n, coins=[1, 3, 4]):
    dp = [0] + [INF] * n
    for i in range(1, n + 1):
        for coin in coins:
            if coin <= i:
                best = dp[i - coin] + 1
                if best < dp[i]:
                    dp[i] = best
    return dp[n]

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.