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

Lập trình động (dynamic programming, DP) là một kỹ thuật thuật toán dùng để giải các bài toán tối ưu bằng cách chia chúng thành các bài toán con đơn giản hơn, rồi tái sử dụng lời giải của các bài toán con đó để giải bài toán ban đầu.

DP thường được dùng cho những bài toán có thể biểu diễn lời giải dưới dạng đệ quy dựa trên các bài toán con nhỏ hơn. Kỹ thuật này được gọi là “động” vì lời giải của các bài toán con có thể được lưu lại và tái sử dụng để giải các bài toán lớn hơn, giúp quá trình này hiệu quả hơn so với việc giải bài toán lớn hơn từ đầu.

DP có thể được dùng cho nhiều loại bài toán, chẳng hạn như đường đi ngắn nhất, dãy con chung dài nhất và mảng con có tổng lớn nhất. Kỹ thuật này đặc biệt hữu ích khi bài toán có các bài toán con chồng lặp và cấu trúc con tối ưu, nghĩa là có thể xây dựng lời giải tối ưu cho bài toán từ các lời giải tối ưu của những bài toán con.