Chương trình động là một phương pháp được dùng trong khoa học máy tính để giải quyết các vấn đề phức tạp bằng cách chia chúng ra thành những phần phụ đơn giản hơn. Nó đặc biệt hiệu quả cho các vấn đề tối ưu hóa và các vấn đề với các chồng chéo nhau và cấu trúc phụ tối ưu. lập trình động bao gồm chọn các kỹ thuật thích hợp, thực hiện tính toán hiệu quả, và hiểu các trường hợp sử dụng thông thường.

Kỹ thuật trong việc lập trình động

Có hai cách tiếp cận chính cho lập trình năng động: từ trên xuống dưới. Cách tiếp cận trên cùng sử dụng sự ghi nhớ để lưu trữ kết quả của các bản sao trong quá trình đệ quy, tránh tính toán thừa. Cách tiếp cận dưới cùng tạo ra các giải pháp tự động từ những tiểu cầu nhỏ nhất, lấp đầy một bảng để tìm câu trả lời cuối cùng.

Tính toán và giải phẫu

Việc thực hiện lập trình năng động đòi hỏi phải xác định trạng thái, đại diện cho một tiểu cầu, và sự chuyển tiếp, mô tả cách tính toán giải pháp cho một trạng thái từ các trạng thái trước. Thông thường, bảng hoặc mảng được dùng để lưu trữ kết quả trung gian. Điều kiện phân loại chính xác và ranh giới là thiết yếu cho tính toán chính xác.

Trường hợp dùng chung

  • Thuật toán đường ngắn nhất, như Dijkstra và Floyd-Warshall
  • Comment
  • Sắp hàng loạt trong tiểu thông tin sinh học
  • Các cây tìm kiếm nhị phân hình chữ nhật
  • Vấn đề thay đổi tiền tệ