Dynamic programming แบ่งปัญหาเป็น sub-problems ยิ่งเล็กยิ่งดี Sub-problems เหล่านี้ไม่ได้แก้แยกกัน แต่ผลลัพธ์ของ sub-problems เล็กๆ ถูกจดจำและนำไปใช้กับ sub-problems ที่ซ้ำหรือทับซ้อนกัน
Dynamic programming ใช้กับปัญหาที่แบ่งเป็น sub-problems คล้ายกันได้ เพื่อ reuse results ส่วนใหญ่ใช้สำหรับ optimization ก่อนแก้ sub-problem ที่มีอยู่ dynamic algorithm จะตรวจสอบผลลัพธ์ของ sub-problems ที่แก้แล้ว Solutions ของ sub-problems ถูกรวมกันเพื่อให้ได้ best solution
สำหรับปัญหาที่ใช้ dynamic programming:
- ปัญหาต้องแบ่งเป็น overlapping sub-problems ได้
- Optimum solution สามารถได้จาก optimum solution ของ sub-problems ย่อย
- Dynamic algorithms ใช้ memorization
Dynamic programming problems แก้ได้ 2 approaches:
- Bottom Up Dynamic programming: วิเคราะห์ปัญหา ดูลำดับที่ sub-problems ถูกแก้ เริ่มจาก trivial sub-problem สร้างขึ้นสู่ปัญหาที่กำหนด
- Top Down Dynamic Programming: เริ่มแก้ปัญหาที่กำหนดโดยแบ่งลงไป ถ้าเห็น sub-problem แก้แล้ว ให้คืนค่าที่เก็บไว้
