Phỏng vấn 4: DP kinh điển và greedy chứng minh
Luyện phỏng vấn DP và greedy: nhận diện bài toán con gối nhau, bảng một hai chiều, chứng minh greedy bằng đổi chỗ.
Chuyên giaThuật toán ~90 phút
Ôn lại trước khi học
Giới thiệu
Bạn luyện quy hoạch động và tham lam. Mỗi bài DP viết đủ 4 bước.
Kiến thức cần nhớ
DP một chiều
- DP một chiều chỉ nhìn về quá khứ gần.
- Hay gặp: bậc thang, cướp nhà, dãy con tăng.
- Ví dụ đời thường: giống leo thang, bước sau dựa bước trước.
- Viết công thức truy hồi trước khi code.
DP hai chiều
- DP hai chiều dùng bảng hàng và cột.
- Hay gặp: đường đi trên lưới, chuỗi con chung, balo.
- Ví dụ đời thường: giống bảng tính Excel điền từng ô.
- Điền đúng thứ tự thì ô sau mới có dữ liệu.
Greedy đúng và sai
- Greedy mỗi bước chọn tốt nhất trước mắt.
- Bài đúng kinh điển: đổi tiền chuẩn, xếp lịch.
- Ví dụ đời thường: greedy như luôn gắp món gần nhất.
- Có bài greedy sai, chỉ DP mới đúng.
# DP bậc thang đơn giản
def leo_thang(n):
a, b = 1, 1 # hai bước gần nhất
for _ in range(n): # lặp n lần
a, b = b, a + b # bước mới bằng tổng hai cũ
return a
Ví dụ
- Mảng 6 số bài một chiều -> bảng dry-run khớp công thức.
- Bài hai chiều -> truy vết ngược dựng được nghiệm cụ thể.
💻 Bài tập
Luyện phỏng vấn, mỗi bài 25 phút. Nộp vào day-164/. Mỗi bài DP viết comment 4 dòng: trạng thái, công thức chuyển, base case, thứ tự tính.
Bài 1: DP một chiều
| Bài | Đề |
|---|---|
| 1a | Cướp nhà: không lấy 2 nhà kề nhau, tổng lớn nhất |
| 1b | Cướp nhà trên vòng tròn (nhà đầu và cuối kề nhau) |
| 1c | Dãy con tăng dài nhất, |
| 1d | Số cách giải mã chuỗi số thành chữ (1 -> A, 26 -> Z) |
1a: [2,7,9,3,1] -> 12
1b: [2,3,2] -> 3
1c: [10,9,2,5,3,7,101,18] -> 4
1d: "226" -> 3
Bài 2: DP hai chiều
| Bài | Đề |
|---|---|
| 2a | Chuỗi con chung dài nhất |
| 2b | Edit distance |
| 2c | Ba lô 0-1, bộ nhớ |
| 2d | Chia mảng thành 2 phần tổng bằng nhau |
2b: "horse", "ros" -> 3
2d: [1,5,11,5] -> true; [1,2,3,5] -> false
Bài 3: Greedy và chứng minh (nâng cao)
| Bài | Đề | Viết thêm |
|---|---|---|
| 3a | Chọn nhiều cuộc họp không chồng nhau nhất | Chứng minh bằng lập luận "đổi chỗ" vì sao chọn kết thúc sớm nhất |
| 3b | Nhảy xa: mảng bước nhảy tối đa, có tới được cuối không | Vì sao greedy đúng |
| 3c | Đổi tiền với mệnh giá [1, 3, 4] | Chỉ ra input greedy sai, giải bằng DP |
3a: [(1,3),(2,4),(3,5),(0,6),(5,7),(8,9)] -> 4
3c: amount = 6 -> greedy 3 đồng (4+1+1), DP 2 đồng (3+3)
✅ Tiêu chí hoàn thành
- 11 bài có test.
- Mỗi bài DP có comment 4 dòng.
- 3a và 3b có lập luận chứng minh viết bằng lời.
- Bảng thời gian thực tế mỗi bài.
❓ Câu hỏi ôn tập
- 4 bước làm bài DP là gì?
- DP hai chiều điền bảng theo thứ tự nào?
- Chứng minh greedy bằng cách nào?
- Nén không gian cần trả lời gì?
🌕 Bạn đã hoàn thành ngày 164. Làm hết bài tập phía trên rồi sang ngày tiếp theo.