Cách tôi tiếp cận bài toán Dynamic Programming

1. Bắt đầu từ câu hỏi mà trạng thái phải trả lời

Tôi luôn cố định nghĩa dp[i] hoặc dp[i][j] bằng ngôn ngữ tự nhiên trước khi viết code. Nếu tôi chưa thể diễn đạt trạng thái thành một câu hoàn chỉnh, nghĩa là lời giải DP vẫn chưa rõ.

Một nguyên tắc hữu ích là: mỗi trạng thái nên trả lời đúng một câu hỏi cụ thể. Ví dụ, “giá trị tốt nhất khi dùng i phần tử đầu tiên” rõ ràng hơn nhiều so với “một giá trị nào đó liên quan đến i phần tử đầu”.

2. Truy ngược xem mỗi trạng thái đến từ đâu

Sau khi định nghĩa trạng thái, tôi liệt kê những trạng thái trước đó có thể chuyển sang nó. Đây thường là nơi diễn ra phần tư duy quan trọng nhất của DP. Nếu chuyển trạng thái cảm thấy gượng ép, có thể định nghĩa trạng thái đang sai.

• Bài toán con nhỏ hơn nào có thể dẫn tới trạng thái hiện tại?
• Ở bước này ta đang ra quyết định gì?
• Quyết định đó làm thay đổi đáp án như thế nào?

3. Xác định thứ tự tính

Khi đã có chuyển trạng thái, tôi quyết định nên dùng bottom-up hay top-down memoization. Trong môi trường thi đấu, tôi thường ưu tiên bottom-up nếu thứ tự tính đơn giản, vì dễ debug hơn.

4. Kiểm tra kỹ base case

Nhiều bài WA đến từ việc base case mơ hồ hoặc không khớp với định nghĩa trạng thái. Tôi luôn kiểm tra xem trạng thái nhỏ nhất có thực sự đúng với câu mô tả trạng thái hay không.

Mẫu tư duy đơn giản

Định nghĩa trạng thái:
dp[i] = đáp án cho i phần tử đầu tiên

Chuyển trạng thái:
dp[i] = tốt nhất giữa (dp[i - 1], dp[i - 2] + value[i])

Base case:
dp[0], dp[1]

Thứ tự tính:
for i từ 2 đến n

Kết luận

Bước tiến lớn nhất của tôi với Dynamic Programming đến từ việc đặt câu hỏi tốt hơn về trạng thái, chứ không phải chỉ ghi nhớ thêm mẫu. Mẫu giúp tăng tốc sau này, nhưng sự rõ ràng phải đến trước.