Chuyển tới nội dung chính

DP 2 chiều (Two-dimensional DP)

Bạn sẽ học được gì

Nhiều bài toán cần hai chỉ số để mô tả một bài con — ví dụ "xét tới ký tự i của chuỗi A và ký tự j của chuỗi B". Khi đó bảng dp trở thành bảng hai chiều dp[i][j]. Bạn sẽ học ba viên ngọc kinh điển: LCS (dãy con chung dài nhất), edit distance (khoảng cách chỉnh sửa), và 0/1 knapsack (bài toán cái túi). Chìa khoá vẫn không đổi: trạng thái + truy hồi, chỉ là trên một lưới.

1. Trực quan: từ dãy ô sang lưới ô​

Ở DP 1 chiều, dp là một hàng ô. Khi bài toán liên quan tới hai đối tượng cùng lúc (hai chuỗi, hoặc "đồ vật + sức chứa còn lại"), một chỉ số là không đủ. Ta dùng một bảng hai chiều, điền từng ô như tô màu một lưới — thường đi từ trái sang phải, trên xuống dưới.

Trạng thái: dp[i][j] = lời giải khi xét tới phần i của đối tượng thứ nhất và phần j của đối tượng thứ hai. Truy hồi: dp[i][j] ghép từ các ô láng giềng phía trên/trái: dp[i-1][j], dp[i][j-1], dp[i-1][j-1].

2. Bài 1 — Dãy con chung dài nhất (LCS)​

Cho hai chuỗi, tìm độ dài dãy con chung dài nhất (giữ thứ tự, không cần liền kề). Ví dụ "ABCBDAB" và "BDCAB" có LCS dài 4 (chẳng hạn "BCAB").

Đặt dp[i][j] = LCS của A[:i] và B[:j] (i ký tự đầu của A, j ký tự đầu của B). Truy hồi:

  • Nếu A[i-1] == B[j-1]: hai ký tự khớp → dp[i][j] = dp[i-1][j-1] + 1.
  • Ngược lại: bỏ một trong hai → dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
   LCS cua "ABC" va "AC":     (hang 0 va cot 0 deu = 0)

        ""  A   C
   "" [  0  0   0 ]
   A  [  0  1   1 ]   A==A -> goc cheo +1 = 1
   B  [  0  1   1 ]   B khac -> max(tren, trai)
   C  [  0  1   2 ]   C==C -> goc cheo (1) +1 = 2

   => LCS = dp[3][2] = 2  ("AC")
🐞 Điền vài ô dp cho LCS("AC", "AC")Bước 1/3
1# A = "AC", B = "AC"
2dp = [[0,0,0],[0,0,0],[0,0,0]]
3# dp[1][1]: A[0]='A' == B[0]='A'
4dp[1][1] = dp[0][0] + 1
5# dp[2][2]: A[1]='C' == B[1]='C'
6dp[2][2] = dp[1][1] + 1
Biến tại bước này
dp[[0,0,0],[0,0,0],[0,0,0]]
👉 Hàng 0 và cột 0 toàn 0 (chuỗi rỗng).
Đang tải trình chạy code…

3. Bài 2 — Khoảng cách chỉnh sửa (edit distance)​

Hỏi: cần ít nhất bao nhiêu thao tác để biến chuỗi A thành B, với ba thao tác chèn, xoá, thay (mỗi thao tác tính 1). Đây là thuật toán đứng sau gợi ý sửa lỗi chính tả.

dp[i][j] = số thao tác tối thiểu biến A[:i] thành B[:j]. Truy hồi:

  • Nếu A[i-1] == B[j-1]: không tốn gì → dp[i][j] = dp[i-1][j-1].
  • Ngược lại lấy 1 + nhỏ nhất của ba lựa chọn: xoá dp[i-1][j], chèn dp[i][j-1], thay dp[i-1][j-1].
   "horse" -> "ros":  dap an = 3
   (horse -> rorse: thay h->r; rorse -> rose: xoa r; rose -> ros: xoa e)
Đang tải trình chạy code…

4. Bài 3 — Bài toán cái túi 0/1 (0/1 knapsack)​

Có n món đồ, món i nặng w[i] và đáng giá v[i]. Túi chịu tối đa W kg. Mỗi món lấy hoặc không (không lấy nửa món). Hỏi giá trị tối đa?

dp[i][c] = giá trị tối đa khi xét i món đầu với sức chứa còn c. Tại món i:

  • Không lấy: dp[i-1][c].
  • Lấy (nếu w[i-1] <= c): v[i-1] + dp[i-1][c - w[i-1]].
   dp[i][c] = max( dp[i-1][c],  v[i-1] + dp[i-1][c - w[i-1]] )
                    ^bo qua mon  ^lay mon (tru bot suc chua)
Đang tải trình chạy code…

5. Phân tích chung​

Bàidp[i][j] nghĩa làKhi khớp / lấyNgược lạiThời gian
LCSLCS của A[:i], B[:j]dp[i-1][j-1]+1max(dp[i-1][j], dp[i][j-1])O(n·m)
Edit distancethao tác min A[:i]→B[:j]dp[i-1][j-1]1 + min(3 hướng)O(n·m)
0/1 knapsackgiá trị max, i món, sức chứa cv+dp[i-1][c-w]dp[i-1][c]O(n·W)

Bẫy thường gặp:

  • Lệch chỉ số: A[i-1] (chuỗi 0-based) ứng với dp[i] (bảng 1-based). Sai chỗ này là sai cả bảng.
  • Quên khởi tạo hàng/cột 0: với edit distance, dp[i][0] = i và dp[0][j] = j rất quan trọng.
  • Knapsack: với loại 0/1 phải duyệt dp[i-1][...] (hàng trước), đừng nhầm sang loại "không giới hạn".

6. Mẫu nhận diện​

  • Bài liên quan tới hai chuỗi (so khớp, biến đổi, chung nhau) → gần như luôn là dp[i][j].
  • "Chọn hoặc không chọn từng món, có ràng buộc tổng (cân nặng/ngân sách)" → knapsack 2 chiều.
  • Trạng thái cần hai con số để mô tả → lưới hai chiều.

7. 🎮 Trò chơi: DP 2 chiều​

🎮 DP 2 chiềuCâu 1/4· Điểm 0· 🔥 0

dp[i][j] dùng hai chỉ số, ghép từ các ô láng giềng trên/trái/chéo.

Edit distance khi hai ký tự KHÁC nhau lấy?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Độ phức tạp của LCS hai chuỗi dài n và m là?
2. Với edit distance, ý nghĩa của dp[0][j] = j là?
3. Trong knapsack 0/1, mỗi món có thể được lấy?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.4.4 — DP trên chuỗi/lưới (đếm đường đi, min path sum, chuỗi con đối xứng).