Thuật toán QUY HOẠCH ĐỘNG 💎Dynamic Programming
Bản chất của Quy hoạch động (Dynamic Programming - DP) có thể hiểu đơn giản qua hai từ khóa cốt lõi: Chia nhỏ và Ghi nhớ. Thay vì giải quyết một vấn đề lớn phức tạp ngay lập tức, ta chia nó thành các bài toán con đơn giản hơn, giải chúng một lần và lưu lại kết quả để tái sử dụng.Dưới đây là các khía cạnh bản chất của kỹ thuật này dưới góc độ lập trình chuyên sâu:
1. Chia bài toán lớn thành các bài toán con trùng lặp
Quy hoạch động thường áp dụng cho các bài toán mà ở đó kết quả của bài toán lớn phụ thuộc trực tiếp vào kết quả của các bài toán con.
Điểm khác biệt so với thuật toán "Chia để trị" (như Merge Sort) là các bài toán con trong Quy hoạch động thường trùng lặp nhau.
Ví dụ: Để tính $F[n]$, bạn cần $F[n-1]$ và $F[n-2]$.
Nhưng để tính $F[n-1]$, bạn lại cần $F[n-2]$ và $F[n-3]$.
Ở đây $F[n-2]$ là bài toán con trùng lặp.
2. Ghi nhớ kết quả (Memoization/Tabulation)Đây là "trái tim" của Quy hoạch động, giúp tối ưu hóa hiệu suất cực lớn bằng cách tránh tính toán lại.Bản chất: Sử dụng một cấu trúc dữ liệu (thường là mảng hoặc bảng) để lưu trữ lời giải của các bài toán con đã được thực hiện.Thực thi: Khi cần lời giải của một bài toán con, chương trình sẽ kiểm tra trong "bảng ghi nhớ" trước. Nếu có rồi, nó lấy ra dùng ngay thay vì tính lại từ đầu.
3. Công thức truy hồi (State Transition)Bản chất của việc liên kết giữa các bài toán con chính là các toán tử logic và số học.Trong lập trình Template Blogspot, điều này tương đương với việc sử dụng các thẻ điều kiện như hoặc toán tử so sánh ==, != để quyết định luồng dữ liệu dựa trên kết quả trước đó.Trong toán học, đây là phương trình thể hiện mối quan hệ giữa các trạng thái (ví dụ: $P[i] = P[i-1] + a[i-1]$ trong bài toán mảng cộng dồn).
Công cụ Mô phỏng Quy hoạch động (Fibonacci)
Bước: 0 / 0
Sẵn sàng minh họa giải thuật Quy hoạch động!