Trong bài blog này, mình cảm ơn bạn Nguyễn Khánh Phúc và Đỗ Anh Khoa đã đóng góp và review bài blog này.

<aside> 💡

Cân nhắc nhẹ:

• Yêu cầu độc giả đã có kiến thức về đệ quy (recursion) và quay lui (backtracking) trong lập trình. </aside>

Khái niệm cơ bản

Quy hoạch động (tên tiếng Anh là “Dynamic Programming”, từ nay về sau tác giả sẽ viết tắt thành cụm từ “DP”) là một kĩ thuật lập trình được sử dụng phổ biến để tối ưu hóa lời giải đệ quy khi các bài toán con giống nhau được gọi lại.

• Ý tưởng cốt lõi đằng sau DP là chứa các lời giải của 1 bài toán con đã được giải trước đó sao cho mỗi lần giải nó chỉ giải một lần (tức là những lần sau nếu nó gọi lại bài toán con giống y hệt thế thì ta chỉ cần lấy kết quả và xử lí thôi, không cần giải lại làm gì!).
• Để giải các bài toán DP, trước hết chúng ta viết ra lời giải đệ quy theo cách bài toán con có thể chồng chất lên nhau trên một cây đệ quy (tức là 1 hàm đệ quy với cùng tham số y hệt được gọi nhiều lần, các bạn sẽ thấy được điều này trong các bài toán sau này).
• Để đảm bảo rằng các giá trị của hàm đệ quy chỉ được tính một lần duy nhất (để cải thiện thời gian thực hiện của thuật toán), ta sẽ lưu trữ kết quả của hàm đệ quy đó lại ở một nơi nào đó (thường là mảng).
• Có hai cách để lưu trữ kết quả của hàm đệ quy, cách thứ nhất gọi là top-down (memoization, ta thường hay gọi nó là “đệ quy có nhớ”) và cách còn lại ta gọi là bottom-up (tabulation).

Khi nào ta sử dụng Quy hoạch động (DP) ?

DP được sử dụng để giải các bài toán có các đặc điểm sau:

1. Optimal Substructure (Cấu trúc phụ/con tối ưu):

Về cơ bản tính chất này có nghĩa là chúng ta sẽ sử dụng kết quả tối ưu của các bài toán con đã xử lí trước đó để thu được kết quả tối ưu cho bài toán lớn hơn.

Ví dụ

Ta xem xét bài toán tìm đường đi có chi phí nhỏ nhất trên một đồ thị có trọng số từ 1 đỉnh nguồn (bắt đầu) đến 1 đỉnh đích (kết thúc).

Bình thường, khi ta thấy bài toán này, trong đầu chỉ nghĩ chăm chăm về một hướng giải là làm sao đó để tìm được đường đi giữa đinh bắt đầu và đỉnh kết thúc, nhưng ta có thể chia nhỏ bài toán ra làm 2 bài toán nhỏ hơn theo hướng như sau:

• Tìm đường đi có chi phí nhỏ nhất từ đỉnh bắt đầu đến đỉnh trung gian.
• Tìm đường đi có chi phí nhỏ nhất từ đỉnh trung gian đến đỉnh kết thúc.