Nền tảng: Big O, Đệ quy, Quay lui, và Quy hoạch động¶

Trước khi đi sâu vào các cấu trúc dữ liệu và thuật toán, ta cần bốn khái niệm nền tảng: ký hiệu Big O để đo hiệu suất, đệ quy để chia nhỏ bài toán thành các bài toán con, quay lui (backtracking) để tìm kiếm toàn bộ kết hợp có cắt tỉa, và quy hoạch động (DP) để tránh tính toán lặp lại. Tệp này sẽ giải thích từng khái niệm từ những nguyên lý đầu tiên.

Các tệp còn lại trong chương này đều giả định bạn đã nắm vững bốn ý tưởng này. Nếu bỏ qua tệp này, những chú thích \(O(n \log n)\), các phép duyệt cây đệ quy, khuôn mẫu quay lui, và chuyển trạng thái DP ở các tệp sau sẽ giống như phép màu hơn là kỹ thuật lập trình.

Tại sao là Mẫu, không phải Học thuộc¶

Trên LeetCode, NeetCode, và HackerRank có hàng ngàn bài toán lập trình. Không ai có thể học thuộc hết, và cố gắng làm thế là một chiến thuật thua cuộc. Người phỏng vấn không chọn bài từ một danh sách cố định — họ chỉnh sửa, kết hợp, và ngụy trang chúng. Một lời giải thuộc lòng cho "Two Sum" sẽ chẳng giúp ích gì khi người phỏng vấn đưa ra một biến thể bạn chưa từng thấy.
Tin tốt là: chỉ có khoảng 15-20 mẫu cốt lõi (hai con trỏ, cửa sổ trượt, BFS/DFS, DP, quay lui, v.v.). Mọi bài toán, dù bề ngoài có vẻ mới lạ đến đâu, đều quy về một hoặc sự kết hợp của các mẫu này. Buổi phỏng vấn không kiểm tra xem bạn đã gặp chính xác bài này chưa. Nó kiểm tra xem bạn có thể gỡ bỏ lớp bối cảnh, câu chuyện, các kiểu dữ liệu cụ thể, các trường hợp đặc biệt, để nhận ra mẫu tiềm ẩn hay không.
Hãy xét ba bài toán sau:
- "Tìm hai số trong một mảng có tổng bằng một giá trị mục tiêu."
- "Tìm hai phân tử có năng lượng liên kết tổng cộng bằng một ngưỡng."
- "Cho một danh sách số dư tài khoản, tìm hai tài khoản có tổng giá trị bằng một khoản nợ."
Chúng trông khác nhau. Nhưng thực chất là cùng một bài toán: Two Sum. Bối cảnh (số, phân tử, tài khoản) là không liên quan. Cấu trúc là: tìm một phần bù trong một tập hợp → tra cứu bản băm (hash map).
Đó là lý do chương này dạy các mẫu thông qua trực giác, chứ không dạy lời giải qua sự lặp lại. Với mỗi mẫu, ta giải thích:
- Thuộc tính cấu trúc nào của bài toán báo hiệu mẫu này (đầu vào đã sắp xếp → hai con trỏ; ràng buộc trên mảng con → cửa sổ trượt; cấu trúc tối ưu + bài toán con chồng chéo → DP).
- Tại sao mẫu lại hoạt động — lập luận toán học hoặc logic, không chỉ là "nó cho kết quả đúng".
- Cách thích nghi — bằng cách chỉ ra các biến thể dễ, trung bình, và khó, nơi cùng một ý tưởng cốt lõi được áp dụng trong các bối cảnh khác nhau.
Khi bạn hiểu sâu tại sao cửa sổ trượt lại hoạt động (tính đơn điệu của ràng buộc nghĩa là việc mở rộng/thu hẹp là đủ), bạn có thể áp dụng nó cho bất kỳ bài toán nào có cấu trúc đó, ngay cả khi chưa từng thấy. Còn nếu chỉ học thuộc code cho "Chuỗi con dài nhất không có ký tự lặp lại", bạn sẽ bế tắc ngay khi đề bài thay đổi.
Chiến thuật thực tế:
1. Học mẫu (chương này).
2. Luyện tập nhận diện trong các bài toán ngụy trang (các bài NeetCode cuối mỗi tệp).
3. Luyện tập triển khai dưới áp lực thời gian.
4. Trong buổi phỏng vấn: đọc đề → gỡ bỏ bối cảnh → xác định mẫu → triển khai.

Ký hiệu Big O¶

Khi ta nói một thuật toán "nhanh" hay "chậm", ta cần một cách đo lường chính xác. Ký hiệu Big O mô tả thời gian chạy (hoặc bộ nhớ sử dụng) của một thuật toán tăng trưởng thế nào khi kích thước đầu vào \(n\) tăng lên, bỏ qua các hằng số và các số hạng bậc thấp.
Định nghĩa hình thức: \(f(n) = O(g(n))\) nghĩa là tồn tại các hằng số \(c > 0\) và \(n_0\) sao cho \(f(n) \leq c \cdot g(n)\) với mọi \(n \geq n_0\). Nói tiếng Việt: \(f\) không tăng nhanh hơn \(g\) đối với các đầu vào lớn.
Tại sao lại bỏ qua hằng số? Vì một thuật toán \(2n\) và một thuật toán \(5n\) đều là \(O(n)\): chúng có cùng cách mở rộng. Trên một máy tính nhanh hơn, các hằng số thay đổi, nhưng cách mở rộng thì không. Big O nắm bắt độ khó vốn có của bài toán, độc lập với phần cứng.

Phân cấp Tốc độ Tăng trưởng¶

Từ nhanh nhất đến chậm nhất:

Big O	Tên	Ví dụ	\(n = 10^6\) phép toán
\(O(1)\)	Hằng số	Truy cập mảng, tra cứu băm	1
\(O(\log n)\)	Logarit	Tìm kiếm nhị phân	20
\(O(n)\)	Tuyến tính	Quét tuyến tính, một vòng lặp đơn	\(10^6\)
\(O(n \log n)\)	Tuyến tính-logarit	Sắp xếp trộn, sắp xếp hiệu quả	\(2 \times 10^7\)
\(O(n^2)\)	Bậc hai	Vòng lặp lồng nhau, duyệt cặp vét cạn	\(10^{12}\) (quá chậm)
\(O(n^3)\)	Bậc ba	Vòng lặp lồng ba lớp, nhân ma trận	\(10^{18}\) (cực kỳ chậm)
\(O(2^n)\)	Hàm mũ	Mọi tập con, quay lui vét cạn	\(10^{301030}\) (bất khả thi)
\(O(n!)\)	Giai thừa	Mọi hoán vị	vô lý

Quy tắc ngón tay cái: máy tính hiện đại thực thi khoảng \(10^8\)–\(10^9\) phép toán đơn giản mỗi giây. Với giới hạn thời gian 1 giây:
- \(O(n)\) hoạt động với \(n \leq 10^8\)
- \(O(n \log n)\) hoạt động với \(n \leq 10^7\)
- \(O(n^2)\) hoạt động với \(n \leq 10^4\)
- \(O(2^n)\) hoạt động với \(n \leq 25\)
Bảng này cho bạn biết ngay lập tức phương pháp của mình có đủ nhanh hay không. Nếu \(n = 10^5\) và lời giải của bạn là \(O(n^2)\), nó sẽ tốn \(10^{10}\) phép toán — quá chậm. Bạn cần một thuật toán tốt hơn.

Cách Phân tích Big O¶

Vòng lặp đơn qua \(n\) phần tử: \(O(n)\).

total = 0
for x in arr:   # n lần lặp
    total += x   # O(1) mỗi lần lặp
# Tổng: O(n)

Vòng lặp lồng nhau: nhân số lần lặp lại với nhau.

for i in range(n):       # n lần lặp
    for j in range(n):   # n lần lặp mỗi cái
        process(i, j)    # O(1)
# Tổng: O(n^2)

Vòng lặp chia đôi: \(O(\log n)\). Mỗi lần lặp giảm một nửa kích thước bài toán, nên cần \(\log_2 n\) lần lặp.

i = n
while i > 0:
    process(i)
    i //= 2
# Tổng: O(log n)

Vòng lặp lồng nhau với vòng trong phụ thuộc vòng ngoài:

for i in range(n):
    for j in range(i):   # j chạy từ 0 đến i-1
        process(i, j)
# Tổng: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n^2)

Đệ quy: viết hệ thức truy hồi và giải nó (chương 13 đã trình bày Định lý Chủ — Master Theorem). Ví dụ, sắp xếp trộn: \(T(n) = 2T(n/2) + O(n) = O(n \log n)\).

Các Cạm bẫy Thường gặp¶

Vòng lặp ẩn: x in list là \(O(n)\) trong Python (quét tuyến tính), nhưng x in set là \(O(1)\). Dùng in trên một danh sách bên trong một vòng lặp cho kết quả \(O(n^2)\), chứ không phải \(O(n)\).

# TỆ: O(n^2) — "in" trên danh sách là O(n)
for x in arr:
    if x in another_list:
        process(x)

# TỐT: O(n) — chuyển sang tập hợp trước
another_set = set(another_list)
for x in arr:
    if x in another_set:
        process(x)

Nối chuỗi: s += c trong Python sao chép toàn bộ chuỗi mỗi lần. Bên trong một vòng lặp \(n\) lần lặp: \(O(1 + 2 + \cdots + n) = O(n^2)\).
Sự chi phối của sắp xếp: nếu thuật toán của bạn sắp xếp (\(O(n \log n)\)) rồi quét tuyến tính (\(O(n)\)), tổng cộng là \(O(n \log n)\) — bước sắp xếp chi phối.
Độ phức tạp phân bổ (amortised): một số thao tác đắt đỏ thỉnh thoảng nhưng rẻ trung bình. Thêm phần tử vào mảng động là \(O(1)\) phân bổ vì lần \(O(n)\) thay đổi kích thước hiếm hoi được trải đều trên \(n\) lần thêm rẻ. Đừng nhầm \(O(1)\) phân bổ với \(O(1)\) trường hợp xấu nhất.

Độ phức tạp Không gian¶

Độ phức tạp không gian tuân theo cùng các quy tắc Big O, nhưng áp dụng cho bộ nhớ thay vì thời gian.
Các thuật toán tại chỗ (in-place) dùng \(O(1)\) không gian thêm (không tính phần đầu vào). Quicksort dùng \(O(\log n)\) không gian (độ sâu ngăn xếp đệ quy). Sắp xếp trộn dùng \(O(n)\) (các mảng tạm để trộn).
Ngăn xếp đệ quy: mỗi lời gọi đệ quy dùng không gian ngăn xếp. Một lời gọi đệ quy sâu \(n\) lớp dùng \(O(n)\) không gian, ngay cả khi mỗi lời gọi không cấp phát thêm bộ nhớ. Đó là lý do DFS đệ quy trên một đồ thị có \(n\) đỉnh dùng \(O(n)\) không gian.
Trong phỏng vấn, luôn nêu cả độ phức tạp thời gian và không gian. Một lời giải \(O(n)\) thời gian, \(O(n)\) không gian thường được chấp nhận, nhưng \(O(n)\) thời gian, \(O(1)\) không gian thì tốt hơn. Người phỏng vấn có thể yêu cầu bạn tối ưu một trong hai.

Đệ quy¶

Đệ quy là khi một hàm tự gọi chính nó để giải một thể hiện nhỏ hơn của cùng một bài toán. Đây là cách tiếp cận tự nhiên nhất cho các bài toán có cấu trúc đệ quy: cây, cấu trúc lồng nhau, chia để trị, và các dãy số học.
Mọi hàm đệ quy đều có hai phần:
1. Trường hợp cơ sở (base case): thể hiện nhỏ nhất có thể giải trực tiếp (không cần đệ quy). Đây là thứ dừng đệ quy.
2. Trường hợp đệ quy: chia bài toán thành các bài toán con nhỏ hơn, giải chúng đệ quy, và kết hợp kết quả.

Ví dụ: Giai thừa¶

def factorial(n):
    if n <= 1:        # base case
        return 1
    return n * factorial(n - 1)  # recursive case

Cách nó thực thi với factorial(4):
- factorial(4) gọi factorial(3)
- factorial(3) gọi factorial(2)
- factorial(2) gọi factorial(1)
- factorial(1) trả về 1 (trường hợp cơ sở)
- factorial(2) trả về 2 * 1 = 2
- factorial(3) trả về 3 * 2 = 6
- factorial(4) trả về 4 * 6 = 24
Mỗi lời gọi được đẩy lên ngăn xếp lời gọi (call stack). Ngăn xếp tăng dần cho đến khi đạt trường hợp cơ sở, rồi tháo dỡ khi mỗi lời gọi trả về. Nếu đệ quy quá sâu (ví dụ factorial(1000000) trong Python), ngăn xếp bị tràn (RecursionError). Giới hạn đệ quy mặc định của Python là 1000.

Cách Tư duy Đệ quy¶

Sự chuyển đổi tư duy then chốt: hãy tin vào đệ quy. Khi viết một hàm đệ quy, hãy giả định lời gọi đệ quy trả về câu trả lời đúng cho bài toán con nhỏ hơn. Nhiệm vụ của bạn chỉ là:
1. Xử lý trường hợp cơ sở.
2. Chia bài toán thành các phần nhỏ hơn.
3. Kết hợp kết quả.
Bạn không cần truy vết qua mọi lời gọi đệ quy trong đầu. Đó cũng giống như cố hiểu một vòng lặp bằng cách thực thi tinh thần mọi lần lặp. Thay vào đó, hãy xác minh: "nếu lời gọi đệ quy cho tôi câu trả lời đúng với đầu vào nhỏ hơn, thì bước kết hợp của tôi có cho câu trả lời đúng với đầu vào đầy đủ không?"

Ví dụ: Đệ quy trên Danh sách liên kết¶

Đảo ngược một danh sách liên kết đệ quy:

def reverse(head):
    if not head or not head.next:   # base case: 0 hoặc 1 node
        return head

    new_head = reverse(head.next)   # đảo ngược phần còn lại
    head.next.next = head           # trỏ node tiếp theo về lại tôi
    head.next = None                # tôi giờ là đuôi
    return new_head

Tin vào đệ quy: reverse(head.next) đảo ngược đúng phần còn lại của danh sách và trả về node đầu mới. Ta chỉ cần gắn node hiện tại vào cuối.

Ví dụ: Đệ quy trên Cây¶

Tính chiều cao của một cây nhị phân:

def height(root):
    if not root:           # base case: cây rỗng có chiều cao 0
        return 0
    left_h = height(root.left)    # chiều cao cây con trái
    right_h = height(root.right)  # chiều cao cây con phải
    return 1 + max(left_h, right_h)  # node này cộng thêm 1 cấp

Khuôn mẫu này — "đệ quy trái, đệ quy phải, kết hợp" — giải quyết phần lớn các bài toán về cây (xem tệp 03).

Đệ quy so với Lặp¶

Mọi thuật toán đệ quy đều có thể chuyển thành phi đệ quy (dùng ngăn xếp tường minh hoặc vòng lặp). Lặp tránh được chi phí ngăn xếp lời gọi và rủi ro tràn ngăn xếp.
Khi nên chọn đệ quy: bài toán có cấu trúc đệ quy tự nhiên (cây, dữ liệu lồng nhau, chia để trị). Lời giải đệ quy gọn gàng và dễ suy luận hơn.
Khi nên chọn lặp: độ sâu đệ quy có thể rất lớn (ví dụ xử lý một danh sách liên kết \(10^6\) node). Lời giải lặp tránh được tràn ngăn xếp.
Đệ quy đuôi (tail recursion): một lời gọi đệ quy là "đệ quy đuôi" nếu nó là thao tác cuối cùng trong hàm (không có công việc nào thực hiện sau khi lời gọi đệ quy trả về). Một số ngôn ngữ (Scheme, Scala) tối ưu lời gọi đuôi để dùng không gian ngăn xếp hằng số. Python không tối ưu lời gọi đuôi, nên đệ quy đuôi trong Python vẫn dùng \(O(n)\) không gian ngăn xếp.

Các Cạm bẫy Thường gặp¶

Cạm bẫy	Ví dụ	Sửa
Thiếu trường hợp cơ sở	Đệ quy vô hạn → tràn ngăn xếp	Luôn định nghĩa khi nào dừng
Sai trường hợp cơ sở	Sai lệch một đơn vị khi phân rã đệ quy	Kiểm thử với các đầu vào nhỏ nhất (0, 1, 2)
Không thu nhỏ bài toán	`f(n)` gọi `f(n)` thay vì `f(n-1)`	Đảm bảo bài toán con nhỏ hơn hẳn
Tính toán dư thừa	Fibonacci: `f(n) = f(n-1) + f(n-2)` tính lại theo cấp số mũ	Dùng ghi nhớ (memoisation → DP)
Giới hạn đệ quy Python	`factorial(10000)` bị crash	Dùng `sys.setrecursionlimit` hoặc chuyển sang lặp

Quay lui (Backtracking)¶

Quay lui là một cách có hệ thống để khám phá mọi lời giải khả thi bằng cách xây dựng chúng tăng dần và bỏ qua các lời giải một phần không thể dẫn đến một câu trả lời hợp lệ.
Hãy hình dung nó như đi qua một mê cung. Ở mỗi ngã rẽ, bạn chọn một đường. Nếu gặp ngõ cụt, bạn quay lại ngã rẽ cuối và thử một đường khác. Bạn không bắt đầu lại từ đầu — bạn quay lui về điểm quyết định gần nhất.

Ba Bước¶

Mọi thuật toán quay lui đều tuân theo cùng một khuôn mẫu:

Chọn (Choose): chọn một ứng viên để mở rộng lời giải một phần hiện tại.
Khám phá (Explore): đệ quy thử xây dựng một lời giải hoàn chỉnh từ ứng viên này.
Bỏ chọn (Unchoose): hoàn tác lựa chọn (quay lui) và thử ứng viên tiếp theo.

def backtrack(state, choices, result):
    if is_complete(state):
        result.append(state.copy())
        return

    for choice in choices:
        if is_valid(choice, state):
            state.add(choice)           # 1. choose
            backtrack(state, choices, result)  # 2. explore
            state.remove(choice)        # 3. unchoose (backtrack)

Bước bỏ chọn là thứ phân biệt quay lui với đệ quy thuần túy. Thiếu nó, trạng thái sẽ tích lũy mọi lựa chọn và bạn không thể khám phá các đường dẫn thay thế.

Khi nào dùng Quay lui¶

Bài toán yêu cầu liệt kê mọi cấu hình hợp lệ: mọi hoán vị, mọi tập con, mọi cách sắp xếp hợp lệ (ví dụ N-Queens).
Bài toán yêu cầu tìm bất kỳ cấu hình hợp lệ nào: giải Sudoku, tìm đường trong mê cung.
Không gian tìm kiếm lớn nhưng có thể được cắt tỉa: hầu hết các lời giải một phần có thể bị loại sớm mà không cần khám phá hoàn toàn.

Cắt tỉa giúp nó nhanh thế nào¶

Nếu không cắt tỉa, quay lui khám phá mọi tổ hợp khả thi — thời gian hàm mũ. Cắt tỉa loại bỏ các nhánh sớm:

for choice in choices:
    if not is_valid(choice, state):
        continue  # CẮT TỈA: bỏ qua toàn bộ cây con này

    state.add(choice)
    backtrack(state, choices, result)
    state.remove(choice)

Trong N-Queens (tệp 05), việc kiểm tra xung đột cột và đường chéo trước khi đặt một quân hậu cắt cây tìm kiếm từ \(n^n\) xuống còn khoảng \(n!\) ứng viên. Với \(n = 8\), đó là 16 triệu → 40.000. Việc cắt tỉa tốt làm cho các thuật toán hàm mũ khả thi với \(n\) vừa phải.

Sinh mọi Tập con (Dạng Quay lui Đơn giản nhất)¶

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # mỗi lời giải một phần đều là một tập con hợp lệ

        for i in range(start, len(nums)):
            path.append(nums[i])        # choose
            backtrack(i + 1, path)       # explore (i+1: không tái sử dụng)
            path.pop()                   # unchoose

    backtrack(0, [])
    return result

Với [1, 2, 3], cây đệ quy:
- [] → [1] → [1,2] → [1,2,3] (quay lui) → [1,3] (quay lui) → [2] → [2,3] (quay lui) → [3]
Mỗi node trong cây là một lời gọi backtrack. Mỗi lá (và node trung gian) sinh ra một tập con. Tổng số tập con: \(2^n\).

Sinh mọi Hoán vị¶

def permutations(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return

        for i in range(len(remaining)):
            path.append(remaining[i])                    # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                                   # unchoose

    backtrack([], nums)
    return result

Tổng số hoán vị: \(n!\). Mỗi cái tốn \(O(n)\) công việc để xây dựng remaining, nên tổng cộng là \(O(n \cdot n!)\).

Các Cạm bẫy Thường gặp¶

Cạm bẫy	Ví dụ	Sửa
Quên sao chép đường dẫn	`result.append(path)` — mọi phần tử chia sẻ cùng một danh sách	`result.append(path[:])` hoặc `path.copy()`
Không quay lui (bỏ chọn)	Trạng thái cứ tăng, các ứng viên sau thấy trạng thái cũ	Luôn `path.pop()` hoặc `state.remove()` sau lời gọi đệ quy
Sai điểm bắt đầu vòng lặp	Tập con có trùng lặp, hoặc hoán vị tái sử dụng không mong muốn	Dùng tham số `start` để tránh quay lại các chỉ số trước
Bỏ qua cắt tỉa	Khám phá các nhánh rõ ràng không hợp lệ	Thêm `if not is_valid: continue` trước lời gọi đệ quy

Quy hoạch động (Dynamic Programming)¶

Quy hoạch động (DP) là một kỹ thuật tối ưu hóa cho các bài toán mà cùng một bài toán con bị giải nhiều lần. Thay vì tính lại, DP giải mỗi bài toán con một lần và lưu kết quả.
DP áp dụng khi một bài toán có hai thuộc tính:
1. Cấu trúc tối ưu (optimal substructure): lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con.
2. Bài toán con chồng chéo (overlapping subproblems): cùng một bài toán con xuất hiện nhiều lần trong đệ quy.

Động lực từ Fibonacci¶

Fibonacci đệ quy ngây thơ:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Với fib(5), cây đệ quy:
- fib(5) gọi fib(4) và fib(3)
- fib(4) gọi fib(3) và fib(2)
- fib(3) được tính hai lần, fib(2) được tính ba lần
Đây là \(O(2^n)\) vì cây phân nhánh ở mọi cấp, và hầu hết các nhánh tính lại cùng một giá trị. Với fib(50), nó tốn hơn \(10^{15}\) phép toán — không khả thi.
Với ghi nhớ (memoisation) (DP từ trên xuống):

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Giờ fib(3) chỉ tính một lần, được lưu, và tra cứu trong các lời gọi sau. Tổng: \(O(n)\) thời gian, \(O(n)\) không gian.
Với lập bảng (tabulation) (DP từ dưới lên):

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Cùng \(O(n)\) thời gian, nhưng xây dựng lời giải từ dưới lên mà không cần đệ quy. Có thể tối ưu tiếp xuống \(O(1)\) không gian vì mỗi giá trị chỉ phụ thuộc vào hai giá trị trước đó.

Công thức DP¶

Với mọi bài toán DP, hãy theo các bước sau:

Định nghĩa trạng thái: dp[i] (hoặc dp[i][j]) đại diện cho điều gì? Đây là bước khó nhất. Trạng thái phải nắm đủ thông tin để đưa ra các quyết định tối ưu.
Viết hệ thức truy hồi: dp[i] liên hệ với các bài toán con nhỏ hơn thế nào? Đây là công thức chuyển trạng thái.
Xác định trường hợp cơ sở: những bài toán con nhỏ nhất nào có thể giải trực tiếp?
Xác định thứ tự lặp: bài toán con nào phải được giải trước bài toán con nào? Từ dưới lên: lặp theo thứ tự đảm bảo các phụ thuộc đã được giải quyết. Từ trên xuống: đệ quy tự xử lý việc này.
Tối ưu không gian (tùy chọn): nếu dp[i] chỉ phụ thuộc vào hàng trước hoặc vài phần tử trước, bạn không cần toàn bộ bảng.

Ví dụ: Quá trình Tư duy¶

Bài toán: cho một mảng các số nguyên dương, tìm tổng lớn nhất của các phần tử không liền kề (House Robber).

Bước 1 — Định nghĩa trạng thái: dp[i] = tổng lớn nhất khi xét các phần tử nums[0..i].

Bước 2 — Viết hệ thức truy hồi: với phần tử \(i\), ta có hai lựa chọn: - Bỏ qua nó: dp[i] = dp[i-1] (tổng tốt nhất không có phần tử \(i\)). - Lấy nó: dp[i] = dp[i-2] + nums[i] (phải bỏ phần tử \(i-1\), rồi cộng phần tử \(i\)).

Vậy: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Bước 3 — Trường hợp cơ sở: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

Bước 4 — Thứ tự lặp: từ trái sang phải (mỗi trạng thái phụ thuộc vào hai trạng thái trước).

Bước 5 — Tối ưu không gian: chỉ cần hai giá trị cuối cùng.

def rob(nums):
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = nums[0], max(nums[0], nums[1])

    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr

    return prev1

Cách Nhận diện Bài toán DP¶

Bài toán yêu cầu một giá trị tối ưu (chi phí nhỏ nhất, lợi nhuận lớn nhất, dãy dài nhất) hoặc một phép đếm (số cách).
Bài toán có các lựa chọn ở mỗi bước (lấy/bỏ qua, đi trái/phải, dùng đồng xu này hay không), và câu trả lời tổng thể tốt nhất phụ thuộc vào các câu trả lời tốt nhất cho bài toán con.
Vẽ cây đệ quy sẽ lộ ra các bài toán con lặp lại.
Vét cạn là hàm mũ, nhưng số trạng thái phân biệt ít hơn nhiều so với số lời gọi đệ quy.

Các Thể loại DP¶

DP 1D: trạng thái phụ thuộc vào một chỉ số duy nhất. Ví dụ: leo cầu thang, kẻ cướp nhà, mảng con lớn nhất.
DP 2D: trạng thái phụ thuộc vào hai chỉ số. Ví dụ: dãy con chung dài nhất (dp[i][j] cho \(i\) ký tự đầu của chuỗi 1 và \(j\) ký tự đầu của chuỗi 2), khoảng cách chỉnh sửa, các bài toán đường đi trên lưới.
DP khoảng (Interval DP): trạng thái là một phạm vi dp[i][j] đại diện cho bài toán con trên arr[i..j]. Ví dụ: nhân chuỗi ma trận, bóng nổ (burst balloons).
DP ba lô (Knapsack DP): trạng thái là một chỉ số vật phẩm và một dung lượng. Ví dụ: ba lô 0/1, đổi tiền, tổng tập con.
DP mặt nạ bit (Bitmask DP): trạng thái bao gồm một mặt nạ bit biểu diễn những phần tử nào đã được dùng. Ví dụ: TSP, bài toán phân công. Không gian trạng thái là \(O(2^n \cdot n)\), khả thi với \(n \leq 20\).

Từ Trên xuống so với Từ Dưới lên¶

	Top-Down (Memoisation)	Bottom-Up (Tabulation)
Cài đặt	Đệ quy + bộ nhớ đệm	Lặp + bảng
Tính toán	Chỉ các bài toán con thực sự cần	Mọi bài toán con đến mục tiêu
Rủi ro tràn ngăn xếp	Có (đệ quy sâu)	Không
Tối ưu không gian	Khó hơn	Dễ hơn (dùng mảng lăn)
Dễ code	Thường tự nhiên hơn (viết đệ quy, thêm bộ nhớ đệm)	Cần nghĩ về thứ tự lặp

Trong phỏng vấn, từ trên xuống thường code nhanh hơn. Trong sản xuất, từ dưới lên thường được ưu tiên vì hiệu năng (không có chi phí đệ quy, hành vi bộ nhớ đệm tốt hơn).

Các Cạm bẫy Thường gặp¶

Cạm bẫy	Ví dụ	Sửa
Sai định nghĩa trạng thái	`dp[i]` không nắm đủ thông tin để ra quyết định	Thêm chiều (ví dụ `dp[i][j]` thay vì `dp[i]`)
Thiếu trường hợp cơ sở	`dp[0]` sai → mọi giá trị sau đều sai	Xác minh trường hợp cơ sở bằng tay
Sai thứ tự lặp	Tính `dp[i]` trước các phụ thuộc của nó	Vẽ các mũi tên phụ thuộc và lặp theo đó
Không khởi tạo `dp` đúng	Dùng 0 khi lẽ ra phải là vô cực (với bài toán min)	`float('inf')` cho cực tiểu hóa, `float('-inf')` cho cực đại hóa
Quên xét tùy chọn "bỏ qua"	Luôn lấy phần tử hiện tại	Hệ thức thường có `max(take, skip)`
Đối số mặc định có thể đổi	`def f(memo={})` chia sẻ bộ nhớ đệm giữa các lời gọi	`def f(memo=None): if memo is None: memo = {}`
Sai lệch một đơn vị trong DP 2D	Truy cập `text1[i]` khi `dp` đánh chỉ số từ 1	`dp` có kích thước `(m+1) x (n+1)`, truy cập `text1[i-1]`

Kết hợp Tất cả¶

Bốn khái niệm này tạo thành một sự tiến triển:
1. Big O cho bạn biết một phương pháp có đủ nhanh hay không.
2. Đệ quy chia bài toán thành các bài toán con.
3. Quay lui là đệ quy + lựa chọn + hoàn tác, dùng cho tìm kiếm toàn bộ.
4. DP là đệ quy + bộ nhớ đệm, dùng cho tối ưu hóa trên các bài toán con chồng chéo.
Khi gặp một bài toán mới:
- Ước tính kích thước đầu vào \(n\). Big O nào là chấp nhận được?
- Nếu vét cạn là hàm mũ và bài toán yêu cầu liệt kê/tìm cấu hình: quay lui (với cắt tỉa để khả thi).
- Nếu vét cạn là hàm mũ, bài toán yêu cầu một giá trị tối ưu hoặc đếm, và bạn thấy các bài toán con chồng chéo: DP.
- Nếu bài toán có cấu trúc chia đôi không gian tìm kiếm: tìm kiếm nhị phân hoặc chia để trị.
- Nếu bài toán trên các dãy có ràng buộc trên mảng con: cửa sổ trượt hoặc hai con trỏ.
- Nếu bài toán cần tra cứu nhanh: bản băm (hash map).