Bottom-Up DP Thắng Recursion: Giải Coin Change trong O(S×n)

Đề bài chỉ cần hai câu. Bạn có các loại đồng xu với mệnh giá khác nhau, mỗi loại có vô hạn chiếc. Tìm số đồng xu ít nhất có thể cộng lại thành một số tiền mục tiêu, hoặc trả về -1 nếu không có tổ hợp nào khả thi.

Sự đơn giản đó gây hiểu nhầm. Cách thử ngây thơ bùng nổ theo cấp số nhân, và cách sửa — cache các bài toán con — chính xác là điều phân biệt bài này với một bài recursion thuần túy. Coin Change là điểm vào kinh điển của unbounded knapsack DP, và đáng để hiểu từ cả bốn góc độ: naïve recursion, memoized recursion, bottom-up tabulation, và framing BFS tìm đường ngắn nhất.

Tại sao constraints quan trọng trước khi đụng vào code

amount <= 10^4 và coins.length <= 12. Hai con số đó ngay lập tức loại bỏ mọi thứ có độ phức tạp factorial hay exponential. Brute-force recursion là O(S^n) trong trường hợp xấu nhất — với S = 10000 và n = 12 thì không cần tính cũng biết là không xong. Constraints đang nói với bạn: O(S × n) là mục tiêu, và cả hai cách tiếp cận DP đều đạt được điều đó.

Bản thân giá trị coin có thể lên đến 2^31 - 1, điều này ảnh hưởng đến một điểm tinh tế: trong vòng lặp bottom-up bạn so sánh coin <= i, và nếu coin vượt quá amount hoàn toàn, coin đó đơn giản là không bao giờ dùng được. Điều kiện kiểm tra xử lý nó mà không cần special-case riêng.

Brute force: pure recursion

Với amount r, thử mọi coin c mà c <= r, recurse trên r - c, và lấy kết quả nhỏ nhất cộng thêm một. Recursion dừng khi r = 0 (trả về 0 — không cần coin nào) hoặc âm (trả về -1 — đường đi không hợp lệ).

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        def helper(remaining: int) -> int:
            if remaining == 0:
                return 0
            if remaining < 0:
                return -1
            min_coins = float('inf')
            for coin in coins:
                if coin <= remaining:
                    result = helper(remaining - coin)
                    if result != -1:
                        min_coins = min(min_coins, result + 1)
            return -1 if min_coins == float('inf') else min_coins
 
        return helper(amount)

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        return Helper(coins, amount);
    }
 
    private int Helper(int[] coins, int remaining) {
        if (remaining == 0) return 0;
        if (remaining < 0) return -1;
        int minCoins = int.MaxValue;
        foreach (int coin in coins) {
            if (coin <= remaining) {
                int result = Helper(coins, remaining - coin);
                if (result != -1)
                    minCoins = Math.Min(minCoins, result + 1);
            }
        }
        return minCoins == int.MaxValue ? -1 : minCoins;
    }
}

Vấn đề hiện ra ngay khi bạn vẽ recursion tree cho coins = [1, 2, 5], amount = 6. helper(3) được gọi từ helper(4) (qua coin 1), từ helper(5) (qua coin 2), và từ nhiều đường khác. Cùng một bài toán con được tính lại hàng chục lần. Ở amount = 100 điều này đã đau rồi; ở amount = 10000 thì không bao giờ xong.

Time: O(S^n). Space: O(S) độ sâu stack.

Memoization: sửa overlapping subproblems

Recursion tree thực ra là một DAG, không phải tree — cùng một node xuất hiện nhiều lần. Cache kết quả tại mỗi giá trị remaining và trả về ngay khi có cache hit.

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        memo: dict[int, int] = {}
 
        def helper(remaining: int) -> int:
            if remaining in memo:
                return memo[remaining]
            if remaining == 0:
                return 0
            if remaining < 0:
                return -1
            min_coins = float('inf')
            for coin in coins:
                if coin <= remaining:
                    result = helper(remaining - coin)
                    if result != -1:
                        min_coins = min(min_coins, result + 1)
            memo[remaining] = -1 if min_coins == float('inf') else min_coins
            return memo[remaining]
 
        return helper(amount)

public class Solution {
    private Dictionary<int, int> _memo = new();
 
    public int CoinChange(int[] coins, int amount) {
        _memo.Clear();
        return Helper(coins, amount);
    }
 
    private int Helper(int[] coins, int remaining) {
        if (_memo.TryGetValue(remaining, out int cached)) return cached;
        if (remaining == 0) return 0;
        if (remaining < 0) return -1;
        int minCoins = int.MaxValue;
        foreach (int coin in coins) {
            if (coin <= remaining) {
                int result = Helper(coins, remaining - coin);
                if (result != -1)
                    minCoins = Math.Min(minCoins, result + 1);
            }
        }
        int finalResult = minCoins == int.MaxValue ? -1 : minCoins;
        _memo[remaining] = finalResult;
        return finalResult;
    }
}

Mỗi giá trị remaining phân biệt từ 0 đến amount giờ chỉ được tính đúng một lần. Recursion tree thu gọn từ exponential xuống tuyến tính theo S.

Time: O(S × n). Space: O(S) cho memo dictionary cộng call stack, có thể đạt độ sâu S trong trường hợp xấu nhất (ví dụ chỉ có mệnh giá coin là 1).

Stack depth vẫn là vấn đề còn lại. Với amount = 10000 và giới hạn recursion mặc định của Python là 1000, code này thực sự crash trừ khi bạn tăng sys.setrecursionlimit. Đó một mình đã là lý do để ưu tiên phiên bản bottom-up trong production.

Bottom-up tabulation: phiên bản tôi sẽ thực sự dùng

Đảo chiều hướng. Thay vì bắt đầu từ amount và recurse xuống, bắt đầu từ 0 và xây dựng lên. Định nghĩa dp[i] là số coin tối thiểu cần để đạt amount i. Recurrence là:

dp[i] = min(dp[i - coin] + 1)   với mỗi coin mà coin <= i và dp[i - coin] != infinity
dp[0] = 0

Hãy trace coins = [1, 2, 5], amount = 11 bằng tay:

Ban đầu: dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
              [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

i=1: coin=1 -> dp[0]+1=1. dp[1]=1
     dp = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

i=2: coin=1 -> dp[1]+1=2; coin=2 -> dp[0]+1=1. dp[2]=1
     dp = [0, 1, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

i=3: coin=1 -> dp[2]+1=2; coin=2 -> dp[1]+1=2. dp[3]=2
     dp = [0, 1, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

i=4: coin=1 -> dp[3]+1=3; coin=2 -> dp[2]+1=2. dp[4]=2
i=5: coin=1 -> dp[4]+1=3; coin=2 -> dp[3]+1=3; coin=5 -> dp[0]+1=1. dp[5]=1
i=6: coin=1 -> dp[5]+1=2; coin=2 -> dp[4]+1=3; coin=5 -> dp[1]+1=2. dp[6]=2
i=7: coin=1 -> dp[6]+1=3; coin=2 -> dp[5]+1=2; coin=5 -> dp[2]+1=2. dp[7]=2
i=8: coin=5 -> dp[3]+1=3; coin=2 -> dp[6]+1=3. dp[8]=3
i=9: coin=5 -> dp[4]+1=3. dp[9]=3
i=10: coin=5 -> dp[5]+1=2. dp[10]=2
i=11: coin=1 -> dp[10]+1=3; coin=5 -> dp[6]+1=3. dp[11]=3

Kết quả: dp[11] = 3  (5 + 5 + 1)

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            foreach (int coin in coins) {
                if (coin <= i && dp[i - coin] != int.MaxValue) {
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == int.MaxValue ? -1 : dp[amount];
    }
}

Lưu ý guard dp[i - coin] != int.MaxValue trong C#. Trong Python, float('inf') + 1 vẫn là float('inf') nên không có rủi ro overflow, nhưng trong C# cộng 1 vào int.MaxValue sẽ wrap around thành int.MinValue và làm hỏng phép tính minimum. Lần đầu tôi viết code này đã bỏ sót điều đó.

Time: O(S × n). Space: O(S) — chỉ cần dp array, không có stack overhead.

Phiên bản bottom-up là thứ tôi sẽ dùng thực tế. Không có vấn đề recursion limit, không có dictionary allocation overhead, memory access tuyến tính cache-friendly, và logic chỉ ba dòng một khi bạn có định nghĩa đúng.

Sơ đồ này nắm bắt cấu trúc reachability chính: dp[5] = 1 là neo giúp cả dp[10] = 2 và dp[11] = 3 đều rẻ. Đường đi 0 -> 5 -> 10 -> 11 (ba coin: 5+5+1) hiện ra tự nhiên.

BFS: tìm đường ngắn nhất trong coin graph

Có một cách nhìn thứ tư đáng biết. Coi bài toán như tìm đường ngắn nhất trong đồ thị không trọng số: các node là amount từ 0 đến amount, và có cạnh từ a đến a + coin với mỗi coin. BFS trên đồ thị này từ node 0 tìm amount với số hop tối thiểu, bằng đúng số coin tối thiểu.

from collections import deque
 
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        if amount == 0:
            return 0
        queue = deque([(0, 0)])  # (amount_hiện_tại, số_bước)
        visited = {0}
        while queue:
            current, steps = queue.popleft()
            for coin in coins:
                nxt = current + coin
                if nxt == amount:
                    return steps + 1
                if nxt < amount and nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, steps + 1))
        return -1

using System.Collections.Generic;
 
public class Solution {
    public int CoinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        var queue = new Queue<(int amount, int steps)>();
        var visited = new HashSet<int> { 0 };
        queue.Enqueue((0, 0));
        while (queue.Count > 0) {
            var (current, steps) = queue.Dequeue();
            foreach (int coin in coins) {
                int nxt = current + coin;
                if (nxt == amount) return steps + 1;
                if (nxt < amount && visited.Add(nxt))
                    queue.Enqueue((nxt, steps + 1));
            }
        }
        return -1;
    }
}

BFS đảm bảo đúng vì nó khám phá các amount theo thứ tự số coin, không bao giờ thăm lại một amount. Set visited là cốt lõi — nếu không có nó, nhiều đường đến cùng một amount đều được đưa vào queue và queue phình lên O(S × n) thay vì O(S).

Time: O(S × n). Space: O(S) cho queue và visited set.

Tôi sẽ chọn BFS hơn DP chỉ khi ai đó đặt bài này rõ ràng như bài toán đồ thị trên whiteboard — mental model chuyển đổi rất gọn và BFS là công cụ quen thuộc. Trong thực tế bottom-up DP nhanh hơn (array vs. hash set overhead) và dùng ít memory hơn.

Edge cases

amount = 0: cả BFS và bottom-up DP đều xử lý được — BFS trả về 0 trước khi chạm vào queue, dp[0] = 0 trực tiếp. Base case của recursion cũng cover.

Không có tổ hợp hợp lệ (coins = [2], amount = 3): dp[1], dp[3] vẫn ở infinity vì không có coin nào đến được chúng từ dp[0]. Kiểm tra cuối trả về -1. BFS cạn kiệt queue mà không bao giờ đụng 3.

Coin duy nhất chia hết amount (coins = [5], amount = 10): dp[5] = 1, dp[10] = 2. Đúng. Nếu không chia hết (coins = [5], amount = 7): dp[5] = 1, dp[6] và dp[7] vẫn ở infinity. Trả về -1.

Giá trị coin rất lớn vượt quá amount: guard coin <= i nghĩa là những coin đó không bao giờ được tham chiếu. Không có rủi ro index-out-of-bounds.

So sánh các approach

Pattern unbounded knapsack

Coin Change là biến thể minimum-cost của bài toán unbounded knapsack. Phần "unbounded" có nghĩa là mỗi item (coin) có thể dùng bao nhiêu lần tùy ý — đó là lý do vòng lặp trong trên coins nằm bên trong vòng lặp ngoài trên amounts thay vì ngược lại, và tại sao dp[i - coin] refer back vào cùng dp array đang được điền thay vì một row trước đó.

Pattern tương tự xuất hiện trong LeetCode 518 (Coin Change II), bài hỏi số cách phân biệt thay vì minimum — recurrence đổi từ min(...) thành sum, nhưng cấu trúc giống hệt. LeetCode 279 (Perfect Squares) là cùng bài toán với coin được thay bằng {1, 4, 9, 16, ...}. LeetCode 377 (Combination Sum IV) đếm các cách có thứ tự để đạt target — thứ tự của các vòng lặp quan trọng ở đó và kết quả là count thay vì minimum. LeetCode 983 (Minimum Cost For Tickets) thêm time-indexed state nhưng cách suy nghĩ về bottom-up table chuyển đổi trực tiếp.

Nếu bạn có thể viết recurrence dp[i] = min(dp[i], dp[i - c] + 1) với c trong items từ trí nhớ, bạn có thể giải cả bốn bài.