برنامه نویسی پویا یک روش است که در علوم کامپیوتر برای حل مشکلات پیچیده با شکستن آنها به زیر مشکلات ساده تر استفاده می شود، به ویژه برای مشکلات بهینه سازی و مشکلات با مشکلات همپوشانی و زیرساخت های بهینه استفاده می شود. پیاده سازی برنامه نویسی پویا شامل انتخاب تکنیک های مناسب، انجام محاسبات موثر و درک موارد استفاده مشترک است.

تکنیک های برنامه نویسی دینامیک

دو رویکرد اصلی برای برنامه نویسی پویا وجود دارد: بالا به پایین و پایین تر. رویکرد بالا به پایین از یادداشت برداری برای ذخیره نتایج مشکلات زیر در طول بازگشت استفاده می کند، اجتناب از محاسبات اضافی. رویکرد پایین به طور غریزی از کوچکترین مشکلات زیر، پر کردن یک جدول برای رسیدن به پاسخ نهایی.

محاسبه ها و اجرای

پیاده سازی برنامه نویسی پویا نیاز به تعریف دولت دارد که نشان دهنده یک مشکل فرعی است و انتقال، که توضیح می دهد چگونه راه حل برای یک دولت از حالت های قبلی را محاسبه کند، به طور معمول، یک جدول یا آرایه برای ذخیره نتایج واسطه ای استفاده می شود.

استفاده مشترک

  • کوتاه ترین الگوریتم های مسیر، مانند Dijkstra و Floyd-Warshall
  • تغییرات مشکل Knapsack
  • هماهنگی در بیوفورماتیک
  • درختان جستجوی باینری
  • مشکل تغییر سکه