Quy hoạch động nâng cao - overlapping, tái cấu trúc nghiệm

Giới thiệu

Bài này học quy hoạch động với ghi nhớ và bảng. Bạn dùng nó để giải ba lô và dãy con chung.

Kiến thức cần nhớ

Hai điều kiện

• Bài toán con gối nhau: nhiều nhánh trùng nhau nên lưu lại đỡ tính lại.
• Cấu trúc con tối ưu: nghiệm lớn chứa nghiệm nhỏ tối ưu.
• Ví dụ đời thường: như lắp Lego, mảnh nhỏ đúng thì khối lớn mới đúng.
• Thiếu 1 trong 2 thì quy hoạch động chuẩn bó tay.

Ghi nhớ và bảng lặp

• Ghi nhớ: giữ đệ quy cũ, thêm từ điển lưu kết quả.
• Bảng lặp: điền từ cơ sở lên đích, đỡ tràn ngăn xếp.
• Ghi nhớ chỉ tính chỗ chạm tới, bảng lặp chạm cả bảng.
• Nén bộ nhớ được khi truy hồi có tính địa phương.

# Ghi nhớ Fibonacci
memo = {}  # lưu kết quả đã tính
def fib(n):
    if n <= 1: return n  # cơ sở
    if n not in memo: memo[n] = fib(n-1) + fib(n-2)  # nhớ để khỏi tính lại
    return memo[n]

Hai truy hồi kinh điển

• Dãy con chung: cuối khớp thì cộng 1, lệch thì lấy max 2 cách bỏ.
• Ba lô 0-1: lấy max giữa bỏ vật và lấy vật cộng phần còn lại.
• Cả 2 đều số trạng thái bằng tích 2 chiều.
• Mỗi trạng thái chỉ vài phép tính nên nhanh hơn liệt kê mũ nhiều.

Truy vết ngược

• Biết giá trị tốt nhất mà không biết chọn vật nào thì chưa xong.
• Đi từ ô đích lần ngược theo quyết định đã ghi.
• Cần bảng quyết định song song bảng giá trị.
• Muốn truy vết đầy đủ thì phải giữ cả bảng, khó nén nhớ.

Ví dụ

• Input: dãy con chung của "" và "abc". Output: 0.
• Giải thích: chuỗi rỗng thì không có gì chung.
• Input: ba lô sức chứa 0. Output: giá trị 0, chọn không vật nào.
• Giải thích: không chỗ chứa thì đành tay trắng.

💻 Bài tập

Ngôn ngữ: C++. Mỗi bài viết bản bảng và dựng lại nghiệm, không chỉ trả giá trị. Nộp vào day-077/.

Bài 1: Dãy con chung dài nhất (LCS)

"ABCBDAB", "BDCABA" -> độ dài 4 (ví dụ "BCBA")
"", "abc"            -> 0, ""

Ứng dụng: viết diff(fileA, fileB) in các dòng thêm +, bớt - dựa trên LCS theo dòng.

Bài 2: Ba lô 0-1

struct Item { std::string name; int weight; int value; };
std::pair<int, std::vector<Item>> knapsack(const std::vector<Item> &items, int W);
int knapsack1D(const std::vector<Item> &items, int W);   // mảng 1 chiều, duyệt w giảm dần

items (nặng, giá): A(1,1) B(3,4) C(4,5) D(5,7), W=7 -> 9, chọn B + C
W=0 -> 0, rỗng

Viết thêm bản vét cạn $2^n$ để kiểm tra với n <= 20.

Bài 3: Edit distance và cắt thanh (nâng cao)

1. editDistance(a, b) với thao tác chèn, xóa, thay, chi phí 1. In dãy thao tác biến a thành b.
2. Cắt thanh dài n, bảng giá p[1..n]. Trả lãi lớn nhất và cách cắt.
3. Với mỗi bài, viết rõ trong comment: trạng thái, công thức chuyển, base case, thứ tự điền bảng.

editDistance("kitten", "sitting") -> 3 (thay k->s, thay e->i, chèn g)
p = [1,5,8,9,10,17,17,20], n=8 -> 22 (cắt 2 + 6)

✅ Tiêu chí hoàn thành

• Test mẫu pass, nghiệm dựng lại đúng giá trị.
• Knapsack khớp vét cạn trên 200 bộ ngẫu nhiên.
• diff in đúng trên 2 file văn bản nhỏ.
• Mỗi bài có comment 4 mục: trạng thái, chuyển, base, thứ tự.

❓ Câu hỏi ôn tập

• Hai điều kiện dùng quy hoạch động là gì?
• Ghi nhớ và bảng lặp khác nhau thế nào?
• Truy hồi ba lô 0-1 viết ra sao?
• Truy vết ngược để làm gì?

🌕 Bạn đã hoàn thành ngày 77. Làm hết bài tập phía trên rồi sang ngày tiếp theo.