Trong hướng dẫn này, bạn sẽ học lập trình động là gì. Ngoài ra, bạn sẽ tìm thấy sự so sánh giữa lập trình động và các thuật toán tham lam để giải quyết vấn đề.
Lập trình động là một kỹ thuật trong lập trình máy tính giúp giải quyết hiệu quả một lớp vấn đề có các bài toán con chồng chéo và thuộc tính cấu trúc con tối ưu.
Những vấn đề như vậy liên quan đến việc tính toán nhiều lần giá trị của các bài toán con giống nhau để tìm ra giải pháp tối ưu.
Ví dụ về lập trình động
Lấy trường hợp tạo chuỗi fibonacci.
Nếu dãy là F (1) F (2) F (3)… F (50), nó tuân theo quy tắc F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Để ý có những bài toán con trùng nhau, chúng ta cần tính F (48) để tính cả F (50) và F (49). Đây chính xác là loại thuật toán mà Lập trình động tỏa sáng.
Cách lập trình động hoạt động
Lập trình động hoạt động bằng cách lưu trữ kết quả của các bài toán con để khi cần đến các giải pháp của chúng, chúng đã sẵn sàng và chúng ta không cần phải tính toán lại.
Kỹ thuật lưu trữ giá trị của các bài toán con này được gọi là ghi nhớ. Bằng cách lưu các giá trị trong mảng, chúng tôi tiết kiệm thời gian tính toán các vấn đề con mà chúng tôi đã gặp phải.
var m = map (0 → 0, 1 → 1) function fib (n) nếu key n không có trong map mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Lập trình động bằng cách ghi nhớ là một cách tiếp cận từ trên xuống đối với lập trình động. Bằng cách đảo ngược hướng mà thuật toán hoạt động tức là bằng cách bắt đầu từ trường hợp cơ sở và hướng tới giải pháp, chúng ta cũng có thể thực hiện lập trình động theo cách từ dưới lên.
function fib (n) if n = 0 return 0 else var prevFib = 0, currFib = 1 lặp lại n - 1 lần var newFib = prevFib + currFib prevFib = currFib currFib = newFib trả về hiện tạiFib
Đệ quy và lập trình động
Lập trình động hầu hết được áp dụng cho các thuật toán đệ quy. Đây không phải là sự ngẫu nhiên, hầu hết các bài toán tối ưu hóa đều yêu cầu đệ quy và lập trình động được sử dụng để tối ưu hóa.
Nhưng không phải bài toán nào sử dụng đệ quy cũng có thể sử dụng Lập trình động. Trừ khi có sự hiện diện của các bài toán con chồng chéo như trong bài toán dãy fibonacci, một phép đệ quy chỉ có thể đạt được lời giải bằng cách sử dụng phương pháp chia và chinh phục.
Đó là lý do tại sao một thuật toán đệ quy như Merge Sort không thể sử dụng Lập trình động, bởi vì các bài toán con không chồng chéo theo bất kỳ cách nào.
Thuật toán tham lam so với lập trình động
Các thuật toán tham lam tương tự như lập trình động theo nghĩa là cả hai đều là công cụ để tối ưu hóa.
Tuy nhiên, các thuật toán tham lam tìm kiếm các giải pháp tối ưu cục bộ hay nói cách khác, một sự lựa chọn tham lam, với hy vọng tìm ra giải pháp tối ưu toàn cầu. Do đó, các thuật toán tham lam có thể đưa ra một dự đoán có vẻ tối ưu vào thời điểm đó nhưng lại trở nên tốn kém và không đảm bảo mức tối ưu trên toàn cầu.
Mặt khác, lập trình động tìm ra giải pháp tối ưu cho các bài toán con và sau đó đưa ra lựa chọn sáng suốt để kết hợp các kết quả của các bài toán con đó để tìm ra giải pháp tối ưu nhất.
