DP 1D — Climbing Stairs, House Robber, Kadane, Coin Change

TL;DR: Bốn bài DP một chiều (climbing stairs, house robber, max subarray của Kadane, coin change) có chung một cấu trúc: dp[i] là đáp án của bài con kết thúc tại hoặc liên quan đến vị trí i, và được tính từ vài dp[j] đứng trước. Transition ngắn (2-3 dòng) nhưng phải xác định đúng ý nghĩa của state. Climbing stairs và house robber nén được xuống O(1) bộ nhớ; coin change thì không, vì phải nhìn lại nhiều state phía trước. Nắm chắc 4 pattern này là bạn đã có nền để xử lý hầu hết bài DP 1D khác.

Bài này áp dụng quy trình 5 bước từ bài trước vào 4 bài cụ thể, trace bảng dp từng bước.

1. Pattern: dp[i] phụ thuộc vài dp trước

Mọi DP 1D đều có transition dạng:

dp[i] <- f(dp[i-1], dp[i-2], ..., dp[i-k])

Các bài chỉ khác nhau ở ý nghĩa của state và hàm f.

2. Climbing Stairs

2.1 Bài toán

Bạn cần lên bậc thang thứ n. Mỗi lần có thể leo 1 bậc hoặc 2 bậc. Hỏi có bao nhiêu cách khác nhau để lên đến bậc n?

Ví dụ: n=4 → 5 cách: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2).

2.2 State và transition

State: dp[i] = số cách leo lên đến bậc i.

Transition: để đến bậc i, bước cuối phải là từ bậc i-1 (leo 1 bậc) hoặc từ bậc i-2 (leo 2 bậc). Hai trường hợp này không giao nhau nên cộng lại:

dp[i] <- dp[i-1] + dp[i-2]

Base case: dp[0] = 1 (1 cách đứng ở mặt đất, tức không bước nào), dp[1] = 1 (1 cách leo lên bậc 1).

2.3 Pseudocode và trace

climbing_stairs(n):
    if n <= 1: return 1
    dp[0] <- 1
    dp[1] <- 1
    for i <- 2 đến n:
        dp[i] <- dp[i-1] + dp[i-2]
    return dp[n]

Time: O(n) Space: O(n), tối ưu xuống O(1)

Trace n=5:

Kết quả: 8 cách leo lên bậc 5. Đây là dãy Fibonacci lệch một vị trí: climbing stairs và Fibonacci có cùng transition.

2.4 Nén bộ nhớ xuống O(1)

dp[i] chỉ cần dp[i-1] và dp[i-2]:

climbing_stairs_opt(n):
    if n <= 1: return 1
    prev2 <- 1    -- dp[0]
    prev1 <- 1    -- dp[1]
    for i <- 2 đến n:
        cur <- prev1 + prev2
        prev2 <- prev1
        prev1 <- cur
    return prev1

Time: O(n) Space: O(1)

Thử ngẫmnếu cầu thang cho phép bước lùi (đi xuống 1 bậc giữa chừng), transition dp[i] = dp[i-1] + dp[i-2] này còn tính đúng số cách nữa không?

3. House Robber

3.1 Bài toán

Có dãy nhà val[0..n-1], mỗi nhà có một số tiền. Không được trộm hai nhà liền kề (hàng xóm sẽ báo cảnh sát). Tìm số tiền lớn nhất lấy được.

Ví dụ: val = [2, 7, 9, 3, 1] → answer 12 (trộm nhà 0, 2, 4: 2+9+1=12).

3.2 State và transition

State: dp[i] = số tiền lớn nhất lấy được khi xét đến nhà i (có thể trộm hoặc bỏ qua nhà i).

Transition: tại nhà i có hai lựa chọn:

• Bỏ qua nhà i: lấy kết quả tốt nhất đến nhà i-1, tức dp[i-1].
• Trộm nhà i: không được trộm nhà i-1, nên lấy kết quả đến nhà i-2 cộng thêm val[i], tức dp[i-2] + val[i].

dp[i] <- max(dp[i-1], dp[i-2] + val[i])

Base case: dp[0] = val[0], dp[1] = max(val[0], val[1]).

3.3 Pseudocode và trace

house_robber(val, n):
    if n = 1: return val[0]
    dp[0] <- val[0]
    dp[1] <- max(val[0], val[1])
    for i <- 2 đến n-1:
        dp[i] <- max(dp[i-1], dp[i-2] + val[i])
    return dp[n-1]

Time: O(n) Space: O(n), tối ưu xuống O(1)

Trace val = [2, 7, 9, 3, 1]:

Đáp án: 12, từ việc trộm nhà 0 (2) + nhà 2 (9) + nhà 4 (1).

Nén bộ nhớ xuống O(1): giữ prev2, prev1 như climbing stairs, với cur <- max(prev1, prev2 + val[i]).

4. Maximum Subarray: Kadane's Algorithm

4.1 Bài toán

Cho mảng A[0..n-1] có thể chứa số âm. Tìm subarray (đoạn con liên tiếp) có tổng lớn nhất.

Ví dụ: A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → answer 6 (subarray [4, -1, 2, 1]).

4.2 State và transition: Kadane

State: dp[i] = tổng lớn nhất của subarray kết thúc tại vị trí i (subarray này bắt buộc chứa A[i]).

Transition: tại vị trí i có hai lựa chọn:

• Bắt đầu subarray mới từ A[i]: chỉ lấy A[i].
• Kéo dài subarray kết thúc tại i-1: dp[i-1] + A[i].

Nếu dp[i-1] âm thì cộng nó vào chỉ làm tổng nhỏ đi, nên bắt đầu lại từ A[i] sẽ tốt hơn.

dp[i] <- max(A[i], dp[i-1] + A[i])

Đáp án là max(dp[0], dp[1], ..., dp[n-1]), chứ không phải dp[n-1].

Base case: dp[0] = A[0].

4.3 Pseudocode và trace

kadane(A, n):
    dp[0] <- A[0]
    best <- A[0]
    for i <- 1 đến n-1:
        dp[i] <- max(A[i], dp[i-1] + A[i])
        best <- max(best, dp[i])
    return best

Time: O(n) Space: O(n), tối ưu xuống O(1)

Trace A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Đáp án: 6, ứng với subarray [4, -1, 2, 1] từ index 3 đến 6.

Nén bộ nhớ xuống O(1): chỉ cần biến cur <- max(A[i], cur + A[i]) và best, không cần mảng.

5. Coin Change: số xu ít nhất

5.1 Bài toán

Cho tập đồng xu coins[] (mỗi mệnh giá dùng được vô hạn lần) và số tiền amount. Tìm số đồng xu ít nhất để ghép đúng bằng amount. Nếu không ghép được, trả về -1.

Ví dụ: coins = [1, 5, 6, 9], amount = 11 → đáp án 2 (5+6).

Vì sao không dùng greedy? Greedy chọn đồng lớn nhất trước: 9, còn 2, rồi 1+1, tổng 3 xu. Nhưng 5+6=11 chỉ cần 2 xu. Greedy sai.

5.2 State và transition

State: dp[i] = số xu ít nhất để ghép đúng bằng i. Nếu không ghép được, dp[i] = INF.

Transition: để ghép được i, đồng xu cuối cùng có thể là bất kỳ đồng c nào trong coins, miễn là i >= c. Khi đó:

dp[i] <- min(dp[i - c] + 1) cho mọi c trong coins, với i >= c

Base case: dp[0] = 0 (cần 0 xu để ghép ra 0).

Đáp án: dp[amount] nếu dp[amount] != INF, ngược lại -1.

5.3 Pseudocode và trace

coin_change(coins, amount):
    dp[0] <- 0
    dp[i] <- INF cho mọi i từ 1 đến amount

    for i <- 1 đến amount:
        for each c trong coins:
            if i >= c and dp[i - c] != INF:
                dp[i] <- min(dp[i], dp[i - c] + 1)

    if dp[amount] = INF: return -1
    return dp[amount]

Time: O(amount × |coins|) Space: O(amount)

Trace coins = [1, 5, 6, 9], amount = 11:

Đáp án: 2 (dùng đồng 5 và đồng 6).

5.4 Tại sao coin change KHÔNG tối ưu về space?

Với climbing stairs và house robber, transition chỉ nhìn lại 1-2 bước nên giữ O(1) state là đủ. Coin change nhìn lại từ i - max_coin đến i - 1, tức tới max_coin bước, nên không giảm xuống O(1) được. Ít nhất phải giữ một cửa sổ cỡ max_coin ô, và khi mệnh giá lớn gần bằng amount thì đó gần như cả mảng dp[0..amount].

Thứ đang so sánh ở đây là bề rộng cửa sổ nhìn lại, và điều quyết định là cửa sổ đó có cố định hay không, chứ không phải nó rộng bao nhiêu. Hai dải trên có bề rộng cố định (2 ô và 1 ô), nên vài biến đơn là đủ thay cho cả mảng. Dải dưới rộng đúng bằng mệnh giá lớn nhất, tức phụ thuộc input: đổi bộ xu là đổi bề rộng. Không có số lượng biến cố định nào đủ dùng, nên cứ giữ cả mảng cho đơn giản.

Thử ngẫmnếu bộ mệnh giá xu trong hệ thống thanh toán của bạn có một đồng trị giá tới 1 triệu, cửa sổ nhìn lại của coin change phình ra bao nhiêu, và mảng dp còn vừa RAM không?

6. Các bẫy hay gặp

Bẫy 1: sai state, dp[i] là "có trộm nhà i" thay vì "tốt nhất đến nhà i"

-- BUG: định nghĩa state là "tiền nếu trộm nhà i"
-- Khi đó dp[3] = dp[1] + val[3] (nhảy 2 bước)
-- Nhưng nghiệm tối ưu có thể bỏ qua nhà 3 hoàn toàn
-- dp[3] với state này không biểu diễn được khả năng bỏ qua nhà 3

-- CORRECT: state là "tiền tối đa khi ĐÃ XÉT đến nhà i, bao gồm hoặc bỏ qua"
dp[i] <- max(dp[i-1], dp[i-2] + val[i])
-- dp[i-1] = bỏ qua nhà i, dp[i-2]+val[i] = trộm nhà i

Bẫy 2: Quên cập nhật best trong Kadane

-- BUG: trả về dp[n-1] thay vì max toàn bộ
kadane_bug(A, n):
    dp[0] <- A[0]
    for i <- 1 đến n-1:
        dp[i] <- max(A[i], dp[i-1] + A[i])
    return dp[n-1]   -- BUG: subarray tốt nhất có thể kết thúc ở bất kỳ vị trí nào

-- CORRECT: track best qua từng bước
    best <- dp[0]
    for i <- 1 đến n-1:
        dp[i] <- max(A[i], dp[i-1] + A[i])
        best <- max(best, dp[i])
    return best

Ví dụ: A = [3, -10, 2] — dp[2] = 2 nhưng answer đúng là 3 (chỉ lấy A[0]).

Bẫy 3: coin change không kiểm tra dp[i - c] != INF trước khi cộng

-- BUG: dp[i-c] = INF (không thể đạt), INF + 1 = overflow hoặc sai
dp[i] <- min(dp[i], dp[i - c] + 1)   -- dp[i-c] có thể là INF

-- CORRECT: guard trước khi cộng
if i >= c and dp[i - c] != INF:
    dp[i] <- min(dp[i], dp[i - c] + 1)

Hai ca biên nên thử tay trước khi nộp: amount = 0 (đáp án 0 xu, không phải -1) và bộ xu không ghép nổi amount. Xem thêm edge case.

Đào sâu

Tóm tắt

• Bốn mẫu 1D: climbing stairs dp[i] = dp[i-1] + dp[i-2], house robber max(dp[i-1], dp[i-2] + val[i]), Kadane max(A[i], dp[i-1] + A[i]), coin change min(dp[i - c] + 1).
• Climbing stairs và house robber nén được xuống O(1) bộ nhớ; coin change thì không.
• Trước khi viết code, hãy nói được bằng một câu dp[i] nghĩa là gì. Sai ở đây là sai hết.
• Kadane: nhớ cập nhật best ở mỗi bước, vì dp[i] chỉ là đoạn kết thúc tại i.

Tự kiểm tra

Bài tiếp theo: DP hai chiều — LCS và Edit Distance