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

درک Dynamic Programming

برنامه نویسی پویا شامل ذخیره نتایج مشکلات فرعی برای جلوگیری از محاسبات اضافی است، این تکنیک زمانی قابل اجرا است که یک مشکل دو ویژگی را نشان می دهد: مشکلات همپوشانی و زیر ساخت مطلوب می تواند با استفاده از یا بالا به پایین (memoization) یا پایین (tabulation) روش ها اجرا شود.

مطالعه موردی: Fibonci Sequence

توالی فیبوناچی یک مثال کلاسیک برای نشان دادن برنامه نویسی پویا است.هدف این است که شماره nth Fiacci را به طور موثر پیدا کنید.

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

برای مثال، برای محاسبه فیبوناچی (۱۰):

فیبوناچی (10) = فیبوناچی (۹) + فیبوناچی (۸)

با ذخیره سازی فیبوناچی (8) و فیبوناچی (9)، محاسبات به حداقل می رسد و منجر به افزایش قابل توجه عملکرد می شود.

مطالعه موردی: مشکلات Knapsack

مشکل 0/1 knapsack شامل انتخاب آیتم هایی با وزن و ارزش های داده شده برای به حداکثر رساندن ارزش کل بدون بیش از حد وزن است.

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

محاسبات شامل جذب آن از طریق اقلام و به روز رسانی جدول بر اساس اینکه آیا از جمله یک آیتم بهبود ارزش کل است.

راهنمایی های پیاده سازی

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

  • شناسایی مشکلات زیر بغل
  • موارد پایه را به صراحت تعریف کنید
  • استفاده از ساختارهای داده مناسب
  • بهینه سازی برای فضا و پیچیدگی زمان