Quy hoạch động là một trong những thuật toán được sử dụng rất nhiều trong các cuộc thi code. Hơn một nửa bài thi trong cuộc thi code đều dùng đến thuật toán này để giải nhanh nhất. Nếu bạn chuẩn bị bước vào kỳ thi này thì đừng bỏ qua bài viết này. Hãy cùng theo dõi bài viết dưới đây để hiểu rõ hơn về thuật toán này nhé!
Khái niệm về quy hoạch động
Quy hoạch động [dynamic programming] là kỹ thuật trong lập trình giúp đơn giản hóa hiệu quả việc chia bài toán lớn thành các bài toán con chồng chéo và cấu trúc con tối ưu. Những bài toán này thường có nhiều nghiệm đúng và mỗi nghiệm có một giá trị đánh giá. Do đó, cần tính toán nhiều lần và sử dụng lời giải của các bài toán con để tìm ra đáp án cho bài toán ban đầu.
Khi bạn muốn giải quyết một bài toán một cách nhanh nhất thì thuật toán này là một cách giải giúp tối ưu thời gian. Quy hoạch động này bao gồm bốn bước như sau:
- Bước 1: Đặc trưng hóa cấu trúc của lời giải tối ưu.
- Bước 2: Định nghĩa giá trị của lời giải tối ưu một cách đệ quy.
- Bước 3: Tính trị của lời giải tối ưu theo kiểu từ dưới lên hoặc trên xuống.
- Bước 4: Xây dựng lời giải tối ưu từ những thông tin đã được tính toán trên.
Tìm hiểu chi tiết về khái niệm quy hoạch động
Thay vì gọi đệ quy, thuật toán sẽ tính toán lời giải của các bài toán con trước tiên và lưu vào mảng bộ nhớ. Tiếp theo, sẽ dùng lời giải của bài toán con trong mảng đã tính trước đó để giải bài toán lớn theo công thức truy hồi. Công thức truy hồi là công thức thể hiện quan hệ giữa các bước trong một bài toán và kết quả của bước sau nhờ vào kết quả của các bước trước đó.
Thuật toán này với ưu điểm chính là tiết kiệm thời gian tính toán thì cũng có một vài nhược điểm. Đầu tiên, việc tìm ra công thức truy hồi hay phân rã bài toán lớn yêu cầu phải suy nghĩ và phân tích thật kỹ càng. Điều này sẽ giúp bạn tránh được sự sai sót cũng như rủi ro phải tính lại từ đầu. Thứ hai là khó xử lý dữ liệu khi bảng lưu trữ yêu cầu mảng hai hoặc ba chiều. Cuối cùng, không phải bài toán tối ưu nào cũng có thể áp dụng giải bằng quy hoạch động.
Bên cạnh đó, một bài toán tối ưu cũng có một số đặc điểm cần lưu ý dưới đây:
- Cần phân tách bài toán lớn thành nhiều bài toán con và kết hợp lời giải của các bài toán con để giải của bài toán lớn.
- Bản chất của thuật toán là giải tất cả các bài toán con. Quy hoạch động không thể tiến hành được nếu không gian lưu trữ không đủ để phối hợp.
Khi nào nên áp dụng thuật toán quy hoạch động?
Điểm quyết định trong khi giải thuật toán này là cần tìm ra được công thức truy hồi cho từng trường hợp bài toán. Đối với một số bài toán thì dễ dàng có nhiều cách giải và giải bằng quy hoạch động nhưng chưa hẳn là giải pháp tối ưu. Mỗi bài toán là mỗi kiểu khó khác nhau, không có một công thức chung cho tất cả các bài toán đó được.
Vậy khi nào chúng ta nên áp dụng đến thuật toán hay ho này? Thường bài toán có hai tính chất này là bạn có thể sử dụng thuật toán quy hoạch động vào. Đó chính là bài toán con gối nhau và cấu trúc con tối ưu.
Bài toán con gối nhau
Bài toán con gối nhau là bài toán nhỏ hơn và được chia từ bài toán ban đầu ra. Việc sử dụng lặp lại nhiều lần này, thuật toán sẽ lưu kết quả mà không cần tính lại, giúp bạn tiết kiệm rất nhiều thời gian. Việc giải một bài toán con nhiều lần thì không thể tránh khỏi việc trùng lời giải của các bài toán con.
Khi các bài toán con không gối nhau thì việc áp dụng thuật toán này cũng bằng không. Quy hoạch động không thể tối ưu được với thuật toán tìm kiếm nhị phân. Lý do vì khi chia bài toán lớn thành các bài toán nhỏ và mỗi bài toán chỉ cần giải một lần mà không được gọi lại.
Bài toán tính Fibonacci là ví dụ rất điển hình của bài toán con gối nhau. Bằng cách cộng fibonacci thứ n-1 và n-2 sẽ tính được số fibonacci thứ n. Bài toán con của số fibonacci thứ n chính là bài toán tính fibonacci n-1 và n-2. Công thức tính toán số Fibonacci được tính như sau:
def fib[n]:
if n