Lập trình động là gì?

Lập trình động, khi đề cập đến lĩnh vực khoa học máy tính, mô tả một nhóm các thuật toán máy tính tương tự nhằm giải quyết các vấn đề phức tạp bằng cách chia vấn đề thành các vấn đề nhỏ hơn.Lần đầu tiên được tạo bởi Richard Bellman vào những năm 1950, lập trình động hoạt động với các vấn đề là các vấn đề phụ chồng chéo hoặc các cấu trúc phụ tối ưu.Để hiểu cách thức lập trình động hoạt động, tốt nhất là hiểu khái niệm đằng sau hai thuật ngữ này. Các biểu tượng phụ chồng chéo mô tả các phương trình phức tạp, khi chia thành các bộ phương trình nhỏ hơn, tái sử dụng các phần của các phương trình nhỏ hơn nhiều lần để đạt được câu trả lời.Ví dụ, một phương trình toán học được yêu cầu tính toán tất cả các kết quả có thể bằng cách sử dụng một tập hợp các số có thể tính toán cùng một kết quả nhiều lần trong khi tính toán các kết quả khác chỉ một lần.Lập trình động sẽ nói với vấn đề này rằng sau khi tính kết quả lần đầu tiên sẽ lưu kết quả đó và cắm câu trả lời vào phương trình sau này thay vì tính toán lại.Khi xử lý các quy trình và phương trình phức tạp dài, điều này sẽ tiết kiệm thời gian và tạo ra một giải pháp nhanh hơn bằng cách sử dụng các bước ít hơn nhiều.Sau khi phá vỡ một vấn đề phức tạp thành các vấn đề nhỏ hơn, máy tính sau đó sử dụng một hệ thống toán học để xác định câu trả lời tốt nhất cho mỗi vấn đề là gì.Nó tính toán câu trả lời cho vấn đề ban đầu từ các câu trả lời nhỏ hơn.Lỗ hổng tồn tại với quá trình này.Mặc dù nó đưa ra giải pháp hoạt động tốt nhất về mặt toán học, nhưng nó có thể hoặc không phải là giải pháp tốt nhất trong cuộc sống thực, tùy thuộc vào loại vấn đề và nó liên quan đến thế giới thực như thế nào.Thuật toán cố gắng tìm con đường ngắn nhất đến giải pháp.Nó có thể mất một trong hai cách tiếp cận để làm điều này.Cách tiếp cận từ trên xuống chia phương trình thành các phương trình nhỏ hơn và sử dụng lại câu trả lời cho các phương trình này khi cần thiết.Cách tiếp cận từ dưới lên cố gắng giải quyết giá trị toán học nhỏ nhất sau khi phá vỡ phương trình xuống và sau đó tiến về phía lớn nhất từ đó.Cả hai cách tiếp cận đều tiết kiệm thời gian, nhưng lập trình động chỉ hoạt động khi vấn đề ban đầu có thể chia thành các phương trình nhỏ hơn mà tại một số điểm được sử dụng lại để giải phương trình.