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 (Kadane), coin change — đều có cấu trúc chung: dp[i] là answer cho subproblem kết thúc tại hoặc liên quan đến vị trí i, và được tính từ một vài dp[j] trước đó. Transition đơn giản (2-3 dòng) nhưng cần xác định đúng ý nghĩa state. Climbing stairs và house robber tối ưu được xuống O(1) space; coin change không thể vì cần xét nhiều state trước. Mastery 4 pattern này là nền tảng để tackle bất kỳ bài DP 1D nào khác.

Bạn đã biết framework 5 bước từ bài trước — state, transition, base case, thứ tự, tối ưu space. Bài này áp dụng framework đó vào 4 bài cụ thể, trace bảng dp từng bước để thấy rõ cơ chế.

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])

Điều khác nhau giữa các bài: ý 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 → cộng lại:

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

Base case: dp[0] = 1 (1 cách đứng ở mặt đất — không bước), 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 đúng là dãy Fibonacci (shifted) — climbing stairs và Fibonacci có cùng transition.

2.4 Tối ưu space 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)

3. House Robber

3.1 Bài toán

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

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 tối đa có thể lấy khi xét đến nhà i (bao gồ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: dp[i-1].
• Trộm nhà i: không thể trộm nhà i-1, lấy kết quả đến nhà i-2 cộng thêm val[i]: 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]:

Answer: 12 — trộm nhà 0 (2) + nhà 2 (9) + nhà 4 (1) = 12.

3.4 Tối ưu space O(1)

house_robber_opt(val, n):
    if n = 1: return val[0]
    prev2 <- val[0]
    prev1 <- max(val[0], val[1])
    for i <- 2 đến n-1:
        cur <- max(prev1, prev2 + val[i])
        prev2 <- prev1
        prev1 <- cur
    return prev1

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

4. Maximum Subarray — Kadane's Algorithm

4.1 Bài toán

Cho mảng A[0..n-1] có thể có số âm. Tìm subarray 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 phải include 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, cộng thêm nó sẽ làm giảm tổng — tốt hơn là bắt đầu lại từ A[i].

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

Answer 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]:

Answer: 6 — subarray [4, -1, 2, 1] từ index 3 đến 6.

Tại sao Kadane hoạt động? Khi dp[i-1] âm, cộng nó chỉ làm tổng nhỏ hơn — tốt hơn là "cắt" và bắt đầu subarray mới từ A[i]. Khi dp[i-1] không âm, kéo dài subarray luôn tốt hơn hoặc bằng bắt đầu lại. Transition max(A[i], dp[i-1] + A[i]) encode chính xác logic này.

4.4 Tối ưu space O(1)

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

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

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à tổng tiền amount. Tìm số đồng xu ít nhất để đạt tổng đúng bằng amount. Nếu không thể, trả về -1.

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

Tại sao không dùng greedy? Greedy chọn đồng lớn nhất trước: 9 → còn 2 → 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 để đạt tổng đúng bằng i. Nếu không thể, dp[i] = INF.

Transition: để đạt tổng 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 để đạt tổng 0).

Answer: 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:

Answer: 2 (dùng coin 5 và coin 6).

flowchart LR
    A0["dp[0]=0"] -->|"+coin 5"| A5["dp[5]=1"]
    A0 -->|"+coin 6"| A6["dp[6]=1"]
    A5 -->|"+coin 6"| A11["dp[11]=2 ✓"]
    A6 -->|"+coin 5"| A11
    A0 -->|"+coin 9"| A9["dp[9]=1"]
    A9 -->|"+coin 1"| A10["dp[10]=2"]
    A10 -->|"+coin 1"| A11

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 → có thể giữ O(1) state. Coin change nhìn lại i - max_coin đến i - 1 — khoảng tới max_coin bước — không thể giảm xuống O(1). Phải giữ toàn bộ mảng dp[0..amount].

6. Pitfall

Pitfall 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 solution tối ưu có thể bỏ qua nhà 3 hoàn toàn
-- dp[3] với state này không capture 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

Pitfall 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]).

Pitfall 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)

7. Liên hệ các bài khác

• DP Framework: Bài này áp dụng framework 5 bước — đọc bài đó trước để hiểu tại sao state và transition được định nghĩa như trên.
• DP 2D — LCS và Edit Distance: Bước tiếp theo: khi state cần 2 chiều (i, j) — cùng tư duy transition nhưng bảng 2D.
• Knapsack: House robber là phiên bản đơn giản của 0/1 knapsack — "chọn hoặc bỏ" với ràng buộc không kề nhau. Knapsack tổng quát thêm chiều "trọng lượng" vào state.
• Recursion và call stack: Hiểu call stack giúp thấy tại sao tối ưu space từ O(n) xuống O(1) quan trọng — khi n lên đến 10^6, mảng O(n) chiếm hàng MB RAM.
• Amortized analysis: Coin change O(amount × |coins|) — amortized O(|coins|) per amount step. Cùng tư duy phân tích tổng chi phí chia đều.

📚 Deep Dive

Tóm tắt

• Climbing stairs: dp[i] = dp[i-1] + dp[i-2] — tổng hai cách đến bước kế trước. Tối ưu O(1) space.
• House robber: dp[i] = max(dp[i-1], dp[i-2] + val[i]) — bỏ qua hoặc trộm nhà i. Tối ưu O(1) space.
• Kadane: dp[i] = max(A[i], dp[i-1] + A[i]) — bắt đầu lại hoặc kéo dài; answer là max qua mọi i.
• Coin change: dp[i] = min(dp[i - c] + 1) qua mọi coin c — không tối ưu được space.
• Pattern chung: xác định đúng ý nghĩa state, viết transition 2-3 dòng, trace bảng tay để verify.
• Tối ưu space O(n) → O(1) khi transition chỉ phụ thuộc vài state gần.

Tự kiểm tra

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