Lesson 26 — Quy hoạch động 2 chiều / Grid

Ba module cho bạn thấy tận mắt bảng dp[i][j] được điền từng ô như thế nào, và mỗi ô lấy giá trị từ đâu (trên / trái / chéo). Đây là lõi của LCS, edit distance và bài toán đường đi trên lưới.

1. Grid path: Min path sum

Lưới chi phí m×n. Bấm Chạy để xem dp[i][j] = grid[i][j] + min(trên, trái) điền từng ô, rồi highlight đường đi tối ưu (xanh lá) từ góc trên-trái xuống dưới-phải.

đang điền đã điền đường tối ưu

Bảng dưới hiển thị cost (góc trên nhỏ) và dp (số lớn). Đường tối ưu = backtrack từ dp[m-1][n-1].

2. LCS table + truy vết

Nhập 2 chuỗi. Bảng điền theo: khớp ký tự ⇒ chéo + 1 (viền tím); khác ⇒ max(trên, trái) (viền xanh). Sau khi điền xong, truy vết tô xanh các ô đường chéo tạo thành LCS.

đang điền khớp (chéo+1) thuộc LCS

3. Edit distance (Levenshtein)

Biến A → B bằng insert / delete / replace. Bảng điền: khớp ⇒ chéo (xanh lá); khác ⇒ 1 + min(chéo=replace, trên=delete, trái=insert). Mỗi ô được tô màu theo thao tác rẻ nhất đã chọn.

Thử: biến "kitten" → "sitting" — bảng ra 3 phép (thay k→s, thay e→i, thêm g): mỗi ô chỉ nhìn đúng 3 ô hàng xóm.

match (chéo) replace delete insert