Quy hoạch động là gì?

Quy hoạch động có tác dụng gì?

Thuật toán quy hoạch động?

Cho một ví dụ bằng code C++ (nhớ ghi rõ đề bài)?

→ Khái niệm: là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau và cấu trúc con tối ưu.

→ Tác dụng: lưu kết quả của bài toán con nên khi được gọi sẽ không cần phải tính lại → làm giảm thời gian tính toán.

→ Thuật toán quy hoạch động là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu.

→ Ví dụ:  bài toán tính số Fibonacci:

def fib(n):

if n <= 1:

return n

return fib(n -1) + fib(n - 2)