Coin Change

Bài toán

Cho các loại đồng xu coins (mệnh giá khác nhau) và một tổng tiền amount. Hỏi cần ít nhất bao nhiêu đồng xu để tạo nên amount? Nếu không thể tạo ra, trả về -1. Giả sử số lượng mỗi loại đồng xu là vô hạn.

Ví dụ:

Input: coins = [1,2,5], amount = 11
Output: 3
Cách: 5 + 5 + 1 = 11

Phân Tích & Tiếp Cận

Tiếp cận tham lam (Greedy) - SAI LẦM

Lấy đồng xu lớn nhất có thể trước? Ví dụ: coins = [1, 3, 4], amount = 6. Greedy: Lấy 4 -> Còn 2 -> Lấy 1, 1 -> Tổng 3 đồng (4+1+1). Tối ưu: Lấy 3, 3 -> Tổng 2 đồng. (Greedy sai).

Dynamic Programming (Bottom-Up)

dp[i] = Số xu ít nhất để tạo ra số tiền i. Ta muốn tính dp[amount]. Để tính dp[i], ta thử từng loại coin c trong coins: dp[i] = min(dp[i], 1 + dp[i - c]) (với điều kiện i - c >= 0).

Base case: dp[0] = 0 (Cần 0 đồng xu để tạo ra 0 đồng). Khởi tạo mảng dp với giá trị amount + 1 (đại diện cho Infinity).

function coinChange(coins: number[], amount: number): number {
    // Fill with amount + 1 (max possible coins is amount using only 1-coins, so amount+1 is like Infinity)
    const dp = new Array(amount + 1).fill(amount + 1);
    
    dp[0] = 0;

    for (let a = 1; a <= amount; a++) {
        for (const c of coins) {
            if (a - c >= 0) {
                dp[a] = Math.min(dp[a], 1 + dp[a - c]);
            }
        }
    }

    // Nếu giá trị vẫn là init value -> Không tìm thấy cách đổi
    return dp[amount] > amount ? -1 : dp[amount];
}

• Time Complexity: $O(amount \cdot len(coins))$.
• Space Complexity: $O(amount)$.

Pattern Nhận Diện

Đây là bài toán Unbounded Knapsack (Cái túi không giới hạn). Một biến thể khác là 0/1 Knapsack (Mỗi vật chỉ được chọn 1 lần) -> Loop ngược chiều. Ở đây mỗi coin chọn bao nhiêu lần cũng được -> Loop xuôi chiều.