Pattern · Quy hoạch động 1 chiềuDễ ~15 phút đọc + làm

Leo Cầu ThangClimbing Stairs

Hiểu bài

Bạn đang leo một cầu thang có n bậc. Mỗi lần bạn có thể bước 1 hoặc 2 bậc. Có bao nhiêu cách khác nhau để bạn leo lên đến bậc thứ n?

Ví dụ:

n = 2
output = 2  // [1+1] hoặc [2]

n = 3
output = 3  // [1+1+1], [1+2], [2+1]

Quan sát: số cách leo lên bậc n = số cách leo lên bậc n-1 (rồi bước 1) + số cách leo lên bậc n-2 (rồi bước 2).

Đây chính là quan hệ truy hồi Fibonacci — bài nhập môn của Quy hoạch động 1 chiều (DP-1D).

Xem cách cơ bản (chậm hơn)

Cách cơ bảnO(2ⁿ) time, O(n) space (call stack)

function climbStairs(n: number): number {
  // Đệ quy thuần — mỗi bước gọi 2 nhánh con
  if (n <= 1) return 1
  return climbStairs(n - 1) + climbStairs(n - 2)
}

Vì sao cách này chậm:

Cây đệ quy có 2 nhánh ở mỗi node, độ sâu n → O(2ⁿ) phép tính.

Nhiều bài toán con được tính lại nhiều lần — đây là lý do cần Quy hoạch động.

Lời giải tối ưu

Tối ưuO(n) time, O(n) space

function climbStairs(n: number): number {
  if (n <= 1) return 1
  const dp = new Array<number>(n + 1)
  dp[0] = 1  // 1 cách để đứng tại bậc 0 (không leo)
  dp[1] = 1  // 1 cách để leo lên bậc 1
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]  // quan hệ truy hồi
  }
  return dp[n]
}

Mấu chốt:

Lưu kết quả từng bậc vào mảng dp để không tính lại.

Mỗi dp[i] chỉ cần 2 giá trị trước — có thể tối ưu thêm xuống O(1) space bằng 2 biến thay vì cả mảng.

Chạy thử từng bước

Chạy thử qua từng bước — bấm vào một bước để xem dòng code tương ứng

1function climbStairs(n: number): number {
2  if (n <= 1) return 1
3  const dp = new Array<number>(n + 1)
4  dp[0] = 1  // 1 cách để đứng tại bậc 0 (không leo)
5  dp[1] = 1  // 1 cách để leo lên bậc 1
6  for (let i = 2; i <= n; i++) {
7    dp[i] = dp[i - 1] + dp[i - 2]  // quan hệ truy hồi
8  }
9  return dp[n]
10}

Trường hợp biên phải nhớ

n=0 — đứng ngay ở đích, 1 cách (không leo).
n=1 — 1 cách duy nhất: bước 1 bậc.
n lớn (ví dụ n=45) — kết quả là số Fibonacci thứ 46 (1.836.311.903), vẫn nằm trong safe integer của JavaScript (~2⁵³).
Tối ưu space: thay dp[] bằng 2 biến prev và curr, tiết kiệm O(n) space xuống O(1).

Câu hỏi phỏng vấn liên quan

Quy hoạch động (DP) áp dụng khi bài có:
1. Bài toán con (sub-problem) chồng lặp — cùng sub-problem giải nhiều lần
2. Cấu trúc tối ưu (optimal substructure) — lời giải tối ưu của bài lớn = tổ hợp lời giải tối ưu của bài con

Nếu chỉ có

→ cần memoization. Nếu có cả
→ DP đúng

DP-1D = state chỉ cần 1 index (i). Mảng dp[] lưu kết quả tại từng vị trí.

Pattern chung:

const dp = new Array(n).fill(0)
dp[0] = base case
for (let i = 1; i < n; i++) {
  dp[i] = f(dp[i-1], dp[i-2], ...)  // transition
}
return dp[n-1]

Ví dụ kinh điển:
- Fibonacci: dp[i] = dp[i-1] + dp[i-2]
- Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]
- House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- Maximum Subarray (Kadane): dp[i] = max(nums[i], dp[i-1] + nums[i])

Mẹo: đa số DP-1D chỉ cần 2 biến cuối (prev, curr) → tối ưu space về O(1).

Top edge case dễ miss:

1. Input rỗng: [] hoặc "" — return null/empty hay throw?
2. Single element: [1] — nhiều thuật toán giả định ≥ 2
3. Toàn bộ trùng: [5, 5, 5, 5] — duplicate handling
4. Đã sorted vs reverse sorted: worst case của quick sort
5. Negative numbers: quên handle khi đề chỉ ví dụ dương
6. Max int / overflow: sum của large numbers
7. Pointer null/undefined: trong linked list / tree
8. Off-by-one: < vs <=, length vs length-1
9. Cycle trong graph: infinite loop nếu không có visited set
10. Concurrent modification: thay đổi mảng đang duyệt

Cách hỏi clarify trong phỏng vấn:
- "Mảng có thể rỗng không?"
- "Có duplicate không?"
- "Có negative không?"
- "Range của giá trị?" (để check overflow)
- "Cần return [] hay null khi không có?"

Mẹo: trình bày edge case xong viết test ngay — chứng minh handle đúng.

Flow chuẩn 8 bước:

1. Nhắc lại đề bằng lời mình. Confirm hiểu đúng.
2. Hỏi constraints: size input, sorted chưa, có duplicate, edge case range.
3. Brute force trước. Đưa ra cách thô O(n²) chứng minh logic đúng.
4. Chỉ ra bottleneck. "Vòng for lồng nhau làm O(n²)".
5. Suggest pattern tối ưu. Hash Map / Two-Pointer / Sliding Window / Binary Search...
6. Code rõ ràng, vừa viết vừa giải thích. Identifier có nghĩa (leftPointer, seen, không phải x, tmp).
7. Dry-run với ví dụ. Chạy code bằng tay trên 1-2 input.
8. Test edge cases + chốt Big-O. Time O(?) Space O(?).

Anti-patterns:
- Im lặng quá 30s
- Code ngay khi chưa hiểu đề
- Optimize sớm khi chưa có baseline
- Bỏ qua edge case rồi mới handle khi interviewer hỏi

Vàng: "Em chưa từng gặp pattern này, nhưng nhìn cấu trúc input em nghĩ có thể thử X..." — interviewer thích thấy bạn reason, không phải trả bài học thuộc.

Tham khảo thêm

Hiểu bài

Bạn đang leo một cầu thang có n bậc. Mỗi lần bạn có thể bước 1 hoặc 2 bậc. Có bao nhiêu cách khác nhau để bạn leo lên đến bậc thứ n?

Ví dụ:

n = 2
output = 2  // [1+1] hoặc [2]

n = 3
output = 3  // [1+1+1], [1+2], [2+1]

Quan sát: số cách leo lên bậc n = số cách leo lên bậc n-1 (rồi bước 1) + số cách leo lên bậc n-2 (rồi bước 2).

Đây chính là quan hệ truy hồi Fibonacci — bài nhập môn của Quy hoạch động 1 chiều (DP-1D).

Lời giải tối ưu

Tối ưuO(n) time, O(n) space

function climbStairs(n: number): number {
  if (n <= 1) return 1
  const dp = new Array<number>(n + 1)
  dp[0] = 1  // 1 cách để đứng tại bậc 0 (không leo)
  dp[1] = 1  // 1 cách để leo lên bậc 1
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]  // quan hệ truy hồi
  }
  return dp[n]
}

Mấu chốt:

Lưu kết quả từng bậc vào mảng dp để không tính lại.

Mỗi dp[i] chỉ cần 2 giá trị trước — có thể tối ưu thêm xuống O(1) space bằng 2 biến thay vì cả mảng.

Chạy thử từng bước

Chạy thử qua từng bước — bấm vào một bước để xem dòng code tương ứng

1function climbStairs(n: number): number {
2  if (n <= 1) return 1
3  const dp = new Array<number>(n + 1)
4  dp[0] = 1  // 1 cách để đứng tại bậc 0 (không leo)
5  dp[1] = 1  // 1 cách để leo lên bậc 1
6  for (let i = 2; i <= n; i++) {
7    dp[i] = dp[i - 1] + dp[i - 2]  // quan hệ truy hồi
8  }
9  return dp[n]
10}

Trường hợp biên phải nhớ

n=0 — đứng ngay ở đích, 1 cách (không leo).

n=1 — 1 cách duy nhất: bước 1 bậc.

n lớn (ví dụ n=45) — kết quả là số Fibonacci thứ 46 (1.836.311.903), vẫn nằm trong safe integer của JavaScript (~2⁵³).

Tối ưu space: thay dp[] bằng 2 biến prev và curr, tiết kiệm O(n) space xuống O(1).

Câu hỏi phỏng vấn liên quan

Nếu chỉ có

→ cần memoization. Nếu có cả
→ DP đúng

DP-1D = state chỉ cần 1 index (i). Mảng dp[] lưu kết quả tại từng vị trí.

Pattern chung:

const dp = new Array(n).fill(0)
dp[0] = base case
for (let i = 1; i < n; i++) {
  dp[i] = f(dp[i-1], dp[i-2], ...)  // transition
}
return dp[n-1]

Mẹo: đa số DP-1D chỉ cần 2 biến cuối (prev, curr) → tối ưu space về O(1).

Top edge case dễ miss:

Mẹo: trình bày edge case xong viết test ngay — chứng minh handle đúng.

Flow chuẩn 8 bước:

Anti-patterns:
- Im lặng quá 30s
- Code ngay khi chưa hiểu đề
- Optimize sớm khi chưa có baseline
- Bỏ qua edge case rồi mới handle khi interviewer hỏi

Vàng: "Em chưa từng gặp pattern này, nhưng nhìn cấu trúc input em nghĩ có thể thử X..." — interviewer thích thấy bạn reason, không phải trả bài học thuộc.

Hiểu bài

Lời giải tối ưu

Chạy thử từng bước

Trường hợp biên phải nhớ

Câu hỏi phỏng vấn liên quan

Bài cùng chủ đề

Tên Trộm Và Dãy Nhà

Dãy Con Tăng Dài Nhất

Tách Chuỗi Thành Từ

Hiểu bài

Lời giải tối ưu

Chạy thử từng bước

Trường hợp biên phải nhớ

Câu hỏi phỏng vấn liên quan

Bài cùng chủ đề

Tên Trộm Và Dãy Nhà

Dãy Con Tăng Dài Nhất

Tách Chuỗi Thành Từ