Min Cost Climbing Stairs: Climbing Stairs với giá vé

Bài trước trong series này đã đi qua Climbing Stairs. Recurrence ở đó là dp[i] = dp[i+1] + dp[i+2] — số cách lên đỉnh từ bậc i bằng tổng số cách từ hai bậc tiếp theo.

Min Cost Climbing Stairs thêm đúng một thứ: mỗi bậc có chi phí. Bạn trả nó khi rời bậc đó. Recurrence trở thành dp[i] = cost[i] + min(dp[i+1], dp[i+2]). Bạn cộng thêm chi phí thay vì đếm đường đi, và lấy min thay vì +. Cùng một bộ khung, hàm kết hợp khác. Pattern này có tên gọi: two-lookback DP. Đáp án tối ưu tại vị trí bất kỳ chỉ phụ thuộc vào đáp án tối ưu tại đúng hai vị trí tiếp theo, không xa hơn, không quay lại.

Đề bài

Cho mảng số nguyên cost trong đó cost[i] là chi phí của bậc thứ i trên cầu thang; sau khi trả chi phí đó, bạn có thể leo một hoặc hai bậc tiếp theo. Bạn có thể bắt đầu từ bậc 0 hoặc bậc 1, và mục tiêu là đến được đỉnh — vị trí ngay sau chỉ số cuối cùng — với tổng chi phí nhỏ nhất. Đề gốc: LeetCode 746.

Ràng buộc:
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999

Bài toán và những gì constraint thực sự buộc ta làm

Cho mảng số nguyên cost trong đó cost[i] là giá của bậc thứ i. Sau khi trả xong, bạn được leo một hoặc hai bậc. Bạn có thể bắt đầu ở chỉ số 0 hoặc 1. Trả về chi phí nhỏ nhất để đạt đỉnh — vị trí ngay sau bậc cuối cùng.

Constraints: 2 <= cost.length <= 1000, 0 <= cost[i] <= 999.

Constraint cost.length <= 1000 quan trọng. Nó loại bỏ brute-force liệt kê tất cả đường đi (2^n đường trong trường hợp xấu nhất, tức 2^1000 — không khả thi), nhưng thoải mái cho phép O(n) và O(n^2). DP O(n) là lựa chọn tự nhiên. Constraint không âm cost[i] >= 0 có nghĩa bạn không bao giờ được lợi từ việc ghé thăm một bậc thêm lần nữa, nên không bao giờ muốn lặp lại — điều này loại bỏ mọi lo lắng về graph có cạnh âm và giữ recurrence gọn gàng. Tổng chi phí tối đa khoảng 999,000, vừa vặn trong 32-bit int, không cần lo overflow.

cost = [10, 15, 20] — đáp án là 15. Bắt đầu ở chỉ số 1, trả 15, nhảy hai bậc thẳng lên đỉnh.

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] — đáp án là 6. Tránh những ô 100 bằng cách nhảy hai bậc mỗi khi cả hai bậc kế tiếp đều rẻ.

Recursion và tại sao nó là điểm khởi đầu đúng

Cách tự nhiên nhất để nghĩ về bài này là đệ quy. Từ bậc i bất kỳ, bạn quyết định: nhảy một bước hay hai? Chi phí của mỗi lựa chọn là cost[i] cộng với chi phí tối ưu từ i+1 (hoặc i+2). Khi đã vượt qua bậc cuối, không còn nợ gì nữa.

Không có memoization, minCost(2) bị tính nhiều lần — một lần qua đường 0->1->2 và một lần qua 0->2 và 1->2. Memoization cắt điều này xuống O(n) bằng cách cache mỗi chỉ số một lần.

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        memo = {}
 
        def min_cost(i: int) -> int:
            if i >= len(cost):
                return 0
            if i in memo:
                return memo[i]
            memo[i] = cost[i] + min(min_cost(i + 1), min_cost(i + 2))
            return memo[i]
 
        return min(min_cost(0), min_cost(1))

public class Solution {
    private Dictionary<int, int> memo = new();
    private int[] cost = null!;
 
    public int MinCostClimbingStairs(int[] cost) {
        this.cost = cost;
        return Math.Min(MinCost(0), MinCost(1));
    }
 
    private int MinCost(int i) {
        if (i >= cost.Length) return 0;
        if (memo.TryGetValue(i, out int cached)) return cached;
        return memo[i] = cost[i] + Math.Min(MinCost(i + 1), MinCost(i + 2));
    }
}

Time: O(n) — mỗi chỉ số chỉ tính một lần. Space: O(n) cho memo dictionary và call stack. Với cost.length <= 1000, độ sâu đệ quy tối đa là 1000, không lo stack overflow. Dù vậy, overhead của các lời gọi hàm và dictionary allocation là không cần thiết khi bạn thấy con đường bottom-up.

Bottom-up DP: điền từ phải sang trái

Đảo hướng lại. Thay vì hỏi "chi phí tối thiểu từ i lên đỉnh là bao nhiêu?", tính sẵn nó cho mọi i bắt đầu từ bậc cuối.

Định nghĩa dp[i] là chi phí tối thiểu để lên đỉnh khi bắt đầu từ bậc i. Base cases: dp[n] = dp[n+1] = 0 — nếu đã ở đỉnh hoặc vượt qua, không nợ gì thêm. Recurrence: dp[i] = cost[i] + min(dp[i+1], dp[i+2]).

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 2)      # dp[n] và dp[n+1] giữ nguyên 0
 
        for i in range(n - 1, -1, -1):
            dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])
 
        return min(dp[0], dp[1])

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n + 2];   // dp[n] và dp[n+1] khởi tạo = 0
 
        for (int i = n - 1; i >= 0; i--)
            dp[i] = cost[i] + Math.Min(dp[i + 1], dp[i + 2]);
 
        return Math.Min(dp[0], dp[1]);
    }
}

Duyệt qua cost = [10, 15, 20] từng bước:

Khởi đầu: dp = [0, 0, 0, 0, 0]   (chỉ số 0..4, dp[3] và dp[4] là hai base case)

i = 2: dp[2] = cost[2] + min(dp[3], dp[4]) = 20 + min(0, 0) = 20
       dp = [0, 0, 20, 0, 0]

i = 1: dp[1] = cost[1] + min(dp[2], dp[3]) = 15 + min(20, 0) = 15
       dp = [0, 15, 20, 0, 0]

i = 0: dp[0] = cost[0] + min(dp[1], dp[2]) = 10 + min(15, 20) = 25
       dp = [25, 15, 20, 0, 0]

Đáp án: min(dp[0], dp[1]) = min(25, 15) = 15

Ở bậc 1, trả 15 và nhảy hai bậc rẻ hơn là trả 10 ở bậc 0 rồi lại trả 15 ở bậc 1 (tổng 25). DP nắm bắt điều này mà không cần đoán mò.

Ví dụ dài hơn cho bức tranh rõ ràng hơn về những gì recurrence thực sự làm. cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]:

i = 9:  dp[9]  = 1   + min(0,    0)   = 1
i = 8:  dp[8]  = 100 + min(1,    0)   = 100
i = 7:  dp[7]  = 1   + min(100,  1)   = 2      <- nhảy qua chỉ số 8
i = 6:  dp[6]  = 1   + min(2,  100)   = 3      <- nhảy qua chỉ số 8
i = 5:  dp[5]  = 100 + min(3,    2)   = 102
i = 4:  dp[4]  = 1   + min(102,  3)   = 4      <- nhảy qua chỉ số 5
i = 3:  dp[3]  = 1   + min(4,  102)   = 5      <- nhảy qua chỉ số 5
i = 2:  dp[2]  = 1   + min(5,    4)   = 5
i = 1:  dp[1]  = 100 + min(5,    5)   = 105
i = 0:  dp[0]  = 1   + min(105,  5)   = 6      <- nhảy qua chỉ số 1

Đáp án: min(dp[0], dp[1]) = min(6, 105) = 6

DP tìm ra con đường rẻ nhất hoàn toàn bằng cách nhảy qua từng ô chi phí 100. Chú ý rằng chỉ số 0 tốt hơn nhiều so với chỉ số 1 làm điểm xuất phát — recurrence truyền điều này một cách tự nhiên.

Time: O(n). Space: O(n).

Space-optimised: hai biến

Recurrence chỉ nhìn lại hai vị trí. Bạn không bao giờ cần dp[i+3] hay trước đó. Vậy mảng là thừa — hai biến là đủ.

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        a, b = 0, 0    # a = dp[i+1], b = dp[i+2]
 
        for i in range(len(cost) - 1, -1, -1):
            a, b = cost[i] + min(a, b), a
 
        return min(a, b)

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int a = 0, b = 0;   // a = dp[i+1], b = dp[i+2]
 
        for (int i = cost.Length - 1; i >= 0; i--)
            (a, b) = (cost[i] + Math.Min(a, b), a);
 
        return Math.Min(a, b);
    }
}

O(n) thời gian, O(1) space. Việc gán đồng thời quan trọng ở đây. Khi tính a mới, bạn cần giá trị cũ của a làm b mới. Trong Python, tuple unpacking xử lý điều này trong một biểu thức. Trong C#, tuple deconstruction làm tương tự. Nếu viết hai câu lệnh tuần tự, b = a sẽ thấy a đã cập nhật và cho ra kết quả sai.

Đây là phiên bản tôi sẽ dùng trong phỏng vấn. Nó cho thấy bạn hiểu recurrence đủ sâu để rút gọn nó — người phỏng vấn thấy bạn không chỉ ghi nhớ công thức.

So sánh cả ba approach

Cả ba đều đạt O(n) vì memoization đảm bảo mỗi chỉ số chỉ tính một lần. Sự khác biệt thực sự duy nhất là space. Tôi sẽ bắt đầu với bottom-up DP trên bảng trắng (trace rõ ràng nhất), rồi đề cập tối ưu hai biến.

Lựa chọn bậc xuất phát không phải edge case

return min(dp[0], dp[1]) xử lý "bạn có thể bắt đầu ở chỉ số 0 hoặc 1". Đây không phải edge case gắn vào cuối — đó là một phần của biên recurrence. Cả hai đều là điểm xuất phát hợp lệ với giá trị chi-phí-lên-đỉnh riêng; đáp án là cái rẻ hơn. Quên điều này và luôn trả về dp[0] sẽ sai với cost = [10, 15, 20] (trả về 25 thay vì 15). Đáng test riêng.

Edge cases và tại sao recurrence xử lý được

Input tối thiểu (cost.length == 2): Chỉ có hai vị trí xuất phát hợp lệ là 0 và 1. dp[0] = cost[0] + min(dp[1], dp[2]) = cost[0] + min(cost[1], 0) = cost[0] (nhảy hai từ 0 không tốn thêm gì ngoài chi phí bậc 0). Đáp án là min(cost[0], cost[1]). Không cần special-casing — công thức hoạt động.

Tất cả chi phí bằng 0: Mọi bậc đều miễn phí. dp[i] = 0 + min(0, 0) = 0 với mọi i. Đáp án là 0. Recurrence chạy hoàn toàn sạch.

Tất cả cùng giá trị v: Mọi con đường đều tốn như nhau. Từ bất kỳ điểm xuất phát nào, con đường tối ưu nhảy hai bậc nhiều nhất có thể. Recurrence vẫn ra đúng mà không cần liệt kê đường đi.

Giá trị lớn tại một bậc duy nhất: Giả sử cost[5] = 999 và mọi thứ khác là 1. DP tự nhiên tránh bậc đó qua min(dp[i+1], dp[i+2]) — nếu nhảy qua bậc 5 tiết kiệm 998, nó sẽ làm vậy. Không cần xử lý đặc biệt.

Tất cả bằng 0 trừ một bậc: Đáp án có thể là 0 nếu bạn nhảy qua bậc đắt bằng bước nhảy hai. Recurrence thấy điều này qua min mà bạn không cần làm gì thêm.

Two-lookback DP như một mental model có thể chuyển giao

Pattern cốt lõi ở đây đơn giản: đáp án tối ưu tại vị trí i chỉ phụ thuộc vào đáp án tối ưu tại đúng i+1 và i+2. Không đâu khác. Lookback hai bước này xuất hiện ở nhiều bài:

• Hàm kết hợp cost[i] + min(...) cho chi phí tối thiểu (bài này).
• Đổi thành + và bạn đếm đường đi — đó là Climbing Stairs (70).
• Đổi thành max(nums[i] + dp[i+2], dp[i+1]) và bạn tối đa hoá tổng không liền kề — đó là House Robber (198).
• Đếm cách giải mã hợp lệ khi mỗi vị trí nhìn lại 1 hoặc 2 ký tự — đó là Decode Ways (91).

Ở tất cả chúng, tối ưu space bằng hai biến áp dụng ngay: khi recurrence chỉ nhìn lại hai bước, bạn không bao giờ cần mảng đầy đủ. Nhận ra độ sâu lookback, không phải hàm kết hợp cụ thể, và bạn có thể rút gọn bất kỳ two-lookback DP nào xuống O(1) space.

Vị trí trong series

Đây là bài thứ hai trong series patterns. Climbing Stairs (bài đầu tiên) giới thiệu two-lookback DP dưới dạng thuần khiết nhất — recurrence đếm không có trọng số. Bài này thêm cost term và đổi + thành min, chuyển bài toán đếm thành bài toán tối ưu mà không hề thay đổi hình dạng recurrence.

Bước tiếp theo trong series là House Robber, bài này thêm constraint: không thể chọn hai phần tử liền kề. Lookback vẫn là hai vị trí, nhưng recurrence giờ có hai nhánh — lấy phần tử hiện tại (nhảy hai) hoặc bỏ qua (tiến một). Sự bất đối xứng đó là nếp gãy mới mà House Robber thêm vào.