برنامهنویسی پویا
برنامهنویسی پویا (Dynamic Programming) یکی دیگر از تکنیکهای حل مسئله است. این روش از این لحاظ که نمونه به نمونههای کوچکتر تقسیم میشود، مشابه روش تقسیم و حل است. ولی در این روش، نخست نمونههای کوچکتر را حل میکنیم، نتایج را ذخیره میکنیم و بعدا هرگاه به یکی از آنها نیاز پیدا شد، بجای محاسبه دوباره کافی است آن را بازیابی کنیم.
اصطلاح برنامهنویسی پویا از نظریه کنترل نشأت میگیرد و در اینجا برنامهنویسی به معنای استفاده از آرایهای (جدولی) است که در آن یک حل بنا میشود. یعنی برنامهنویسی به معنای یک زبان نیست. همانطور که گفتیم در برنامهنویسی پویا، حل را از پایین به بالا در یک آرایه (یا یک سری آرایه) ارائه میکنیم. بنابراین برنامهنویسی پویا یک روش پایین به بالا است. مراحل بسط یک الگوریتم برنامهنویسی پویا به شکل زیر است:
1) ارائه یک ویژگی بازگشتی برای حل نمونهای از مسئله.
2) حل نمونهای از مسئله به شیوه پایین به بالا با حل نمونههای کوچکتر.