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

DP trên chuỗi và lưới (Grid & String DP)

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

DP trên lưới là một họ bài toán cực kỳ trực quan: bạn đứng ở một ô và chỉ được đi theo vài hướng cho phép (thường sang phải và xuống dưới). Mỗi ô lưu lời giải tối ưu để tới được ô đó. Bạn sẽ học ba bài: đếm số đường đi, tổng đường đi nhỏ nhất (min path sum), và một bài DP trên chuỗi rất đẹp — chuỗi con đối xứng (palindrome) dài nhất.

1. Trực quan: ô này tới từ đâu?​

Trên lưới, câu hỏi cốt lõi cho mỗi ô là: "tôi có thể bước vào ô này từ những ô nào?" Nếu chỉ được đi phải và xuống, thì ô (i, j) chỉ có thể tới từ ô trên (i-1, j) hoặc ô trái (i, j-1). Mọi truy hồi trên lưới đều mọc ra từ quan sát đơn giản này.

        (i-1, j)
            |
            v
   (i,j-1) -> (i, j)      o (i,j) den tu TREN hoac TRAI

2. Bài 1 — Đếm số đường đi​

Lưới m × n, robot ở góc trên-trái, chỉ đi phải hoặc xuống, đếm số đường tới góc dưới-phải.

dp[i][j] = số đường tới ô (i, j). Vì tới (i, j) chỉ từ trên hoặc trái:

   dp[i][j] = dp[i-1][j] + dp[i][j-1]

   Hang dau va cot dau toan 1 (chi 1 cach di thang):

      1   1   1   1
      1   2   3   4
      1   3   6  10
      1   4  10  20   <- 20 duong toi goc duoi-phai (luoi 4x4)
🐞 Đếm đường: điền hàng thứ hai của lưới 4×4Bước 1/4
1# dp da co hang 0 va cot 0 toan 1
2dp = [[1,1,1,1],
3    [1,0,0,0]]
4for j in range(1, 4):
5  dp[1][j] = dp[0][j] + dp[1][j-1]
Biến tại bước này
dp[0][1,1,1,1]
dp[1][1,0,0,0]
👉 Hàng 0 toàn 1, cột 0 = 1.
Đang tải trình chạy code…

3. Bài 2 — Tổng đường đi nhỏ nhất (min path sum)​

Mỗi ô lưới mang một chi phí. Đi từ góc trên-trái xuống góc dưới-phải (chỉ phải/xuống), tìm tổng chi phí nhỏ nhất.

dp[i][j] = tổng nhỏ nhất để tới (i, j). Tới (i, j) từ ô rẻ hơn trong hai ô trên/trái, rồi cộng chi phí ô hiện tại:

   dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] )

   grid:            dp (tong nho nhat):
   1  3  1          1  4  5
   1  5  1    ->    2  7  6
   4  2  1          6  8  7    <- dap an 7 (duong 1->3->1->1->1)
Đang tải trình chạy code…

4. Bài 3 — Chuỗi con đối xứng dài nhất (longest palindromic substring)​

Một palindrome là chuỗi đọc xuôi ngược như nhau ("aba", "abba"). Tìm chuỗi con liền kề đối xứng dài nhất trong một chuỗi cho trước.

Đặt dp[i][j] = True nếu đoạn từ i tới j là palindrome. Quan sát: đoạn i..j đối xứng khi hai đầu khớp s[i] == s[j] và phần lõi bên trong i+1 .. j-1 cũng đối xứng:

   dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1]

   "babad":  cac doan do la palindrome:
      "b","a","b","a","d" (do dai 1)
      "bab" (i=0,j=2): s[0]=s[2]='b' va loi "a" doi xung -> True
      "aba" (i=1,j=3): tuong tu -> True
   => dai nhat: "bab" hoac "aba", do dai 3

Vì dp[i][j] cần dp[i+1][j-1] (đoạn ngắn hơn), ta duyệt theo độ dài tăng dần.

Đang tải trình chạy code…

5. Phân tích chung​

Bàidp[i][j] nghĩa làTruy hồiThời gian
Đếm đườngsố đường tới (i,j)dp[i-1][j] + dp[i][j-1]O(m·n)
Min path sumtổng nhỏ nhất tới (i,j)grid[i][j] + min(trên, trái)O(m·n)
Palindromeđoạn i..j có đối xứng khôngs[i]==s[j] and dp[i+1][j-1]O(n^2)

Bẫy thường gặp:

  • Quên khởi tạo hàng đầu / cột đầu trên lưới (chúng chỉ có một hướng đi tới).
  • Với palindrome, thứ tự duyệt phải theo độ dài tăng dần, nếu không dp[i+1][j-1] chưa được tính.
  • Trường hợp đặc biệt độ dài 2 ("bb"): không có "lõi" bên trong nên xử lý riêng.

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

  • Đề có lưới/bàn cờ và đi theo hướng cố định → DP lưới với dp[i-1][j], dp[i][j-1].
  • "Đếm số đường", "đường rẻ nhất/đắt nhất" trên bảng → DP lưới.
  • Câu hỏi về đoạn con đối xứng / con liền kề trên chuỗi → DP trên đoạn [i, j].

7. 🎮 Trò chơi: DP chuỗi/lưới​

🎮 DP trên chuỗi và lướiCâu 1/4· Điểm 0· 🔥 0

Trên lưới: ô tới từ trên/trái. Trên chuỗi: xét đoạn [i, j].

Min path sum: truy hồi đúng là?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Trên lưới chỉ đi phải/xuống, ô (i,j) tới được từ những ô nào?
2. Bài đếm số đường đi dùng phép toán gì để gộp?
3. Vì sao bài palindrome phải duyệt theo độ dài tăng dần?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.4.5 — Tối ưu không gian DP (cuộn mảng: giảm bộ nhớ từ O(n·m) xuống O(m)).