Quy hoạch động: bài toán con gối nhau và memo

Giới thiệu

Bài này học cách giải từ bài nhỏ đi lên. Bạn dùng bảng nhớ để khỏi tính lại.

Kiến thức cần nhớ

Từ dưới lên khác từ trên xuống

• Chia để trị bổ bài lớn thành mảnh độc lập.
• Quy hoạch động giải bài nhỏ rồi dựng bài lớn.
• Hợp khi bài con gối nhau, lặp lại nhiều lần.
• Ví dụ đời thường: xây tường từ viên gạch nhỏ.

Đệ quy + ghi nhớ

• Đệ quy gọi lại chính mình trên bản nhỏ hơn.
• Ghi nhớ cất đáp án, gặp lại thì lấy ra.
• Không nhớ thì cây gọi phình theo mũ.
• Ví dụ đời thường: làm 1 lần rồi photo dùng lại.

Hai điều kiện dùng

• Bài lớn dựng được từ đáp án bài con tối ưu.
• Cùng 1 bài con xuất hiện lặp đi lặp lại.
• Ví dụ dùng: giao hàng, đường bay, chia tài xế.
• Thiếu 2 điều này thì đừng dùng bảng nhớ.

Ví dụ

• Input: tính số hạng 5 không memo và có memo. Output: không memo gọi mũ, có memo gọi tuyến tính.
• Giải thích: mỗi bài con chỉ tính đúng 1 lần.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-017/. Mỗi bài viết 2 bản: đệ quy có memo (top-down) và bảng (bottom-up).

Bài 1: Leo cầu thang

Leo n bậc, mỗi bước 1 hoặc 2 bậc. Đếm số cách.

n=1 -> 1; n=2 -> 2; n=5 -> 8; n=45 -> 1836311903
n=30: calls_naive > 1 triệu, memo mỗi n tính 1 lần

Bài 2: Đổi tiền

Cho mệnh giá coins và số tiền amount.

1. int minCoins(coins, amount): số đồng ít nhất, không đổi được trả -1.
2. long long countWays(coins, amount): số cách đổi (không tính thứ tự).
3. std::vector<int> reconstruct(coins, amount): trả danh sách đồng cụ thể của nghiệm ít nhất.

coins=[1,5,10,25], amount=63 -> minCoins=6 (25,25,10,1,1,1)
coins=[2], amount=3          -> -1
coins=[1,2,5], amount=5      -> countWays=4
coins=[1,3,4], amount=6      -> minCoins=2 (3,3); tham lam chọn 4,1,1 = 3 đồng

Bài 3: Lưới có chướng ngại (nâng cao)

Lưới m x n, ô 1 là đá. Robot đi từ góc trên trái tới góc dưới phải, chỉ sang phải hoặc xuống.

1. Đếm số đường đi.
2. Mỗi ô có chi phí. Tìm đường chi phí nhỏ nhất và in đường đi.
3. Giảm bộ nhớ bảng từ $O(mn)$ xuống $O(n)$.

[[0,0,0],
 [0,1,0],
 [0,0,0]]   -> 2 đường

chi phí [[1,3,1],[1,5,1],[4,2,1]] -> 7, đường (0,0)(0,1)(0,2)(1,2)(2,2)

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

• Test mẫu pass cho cả bản memo và bản bảng.
• Mỗi bài ghi rõ: trạng thái dp[i] nghĩa là gì, công thức chuyển, base case.
• Bài 2 chỉ ra được input mà tham lam sai.
• Nói được 2 điều kiện dùng quy hoạch động bằng ví dụ trong bài.

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

• Quy hoạch động đi từ đâu lên đâu?
• Memo là gì, đặt ở đâu trong hàm?
• Hai điều kiện dùng là gì?
• Đúng trước hay tối ưu trước?

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