برنامه‌نویسی پویا
ویژگی‌ها > زیرمسئله‌های هم‌پوشان

زیرمسئله‌های هم‌پوشان به معنای کوچک بودن فضای زیرمسئله‌هاست، به این معنا که هر الگوریتم بازگشتی برای حل این مسئله، باید به جای ایجاد زیرمسئله‌های جدید، زیرمسئله‌های تکراری را بارها حل کند. برای مثال، به فرمول بازگشی دنبالهٔ فیبوناچی دقت کنید: Fi = Fi−1 + Fi−2، با حالات پایهٔ F1 = F2 = ۱. آنگاه F43 = F42 + F41، و F42 = F41 + F40. اکنون F41 در زیردرخت‌های هر دوی F43 و F42 محاسبه می‌شود. در صورت اتخاذ چنین رویکرد ساده‌انگارانه‌ای، نهایتاً زیرمسئله‌های یکسانی را بارها حل می‌کنیم، در صورتی که تعداد کل زیرمسئله‌ها در واقعیت کم است (تنها ۴۳تا). برنامه‌نویسی پویا به این حقیقت دقت می‌کند و هر زیرمسئله را تنها یک بار حل می‌کند.
گفته می‌شود مسئله‌ای دارای زیرمسئله‌های هم‌پوشان است، اگر بتوان مسئله را به زیرمسئله‌های کوچکتری شکست که پاسخ هرکدام چند بار در طول فرایند حل مورد استفاده قرار بگیرد. برنامه‌ریزی پویا کمک می‌کند تا هر کدام از این پاسخ‌ها فقط یک بار محاسبه شوند و فرایند حل از بابت دوباره‌کاری هزینه‌ای را متحمل نشود. برای مثال در دنباله فیبوناچی برای محاسبهٔ عدد چهارم دنباله به دانستن عدد سوم نیاز داریم. برای محاسبهٔ عدد پنجم هم باز به عدد سوم نیاز داریم. حال اگر مثلاً در شرایطی بخواهیم عدد ششم دنبالهٔ فیبوناچی را حساب کنیم، در این محاسبه هم مقدار عدد پنجم را می‌خواهیم و هم مقدار عدد چهارم را. اگر تصمیم بگیریم اعداد چهارم و پنجم را به نوبت حساب کنیم در هنگام محاسبهٔ هرکدام به مقدار عدد سوم نیاز پیدا می‌کنیم و باید دوباره آن را محاسبه کنیم.
برای جلوگیری از این محاسبات چندباره، الگوریتمهایی که مبتنی بر برنامه‌ریزی پویا هستند، معمولاً یکی از دو راه زیر را استفاده می‌کنند.
رویکرد بالا به پایین: راه درروی مستقیم از صورت‌بندی بازگشتی هر مسئله‌ای است. اگر جواب مسئله‌ای را بتوان به صورت بازگشتی با جواب زیرمسئله‌های آن به دست آورد، و در صورت هم‌پوشانی زیرمسئله‌ها، می‌توان جواب زیرمسئله‌ها را در یک جدول به خاطر سپرد. هر گاه که برای حل یک زیرمسئله اقدام می‌کنیم، ابتدا بررسی می‌کنیم که آیا این زیرمسئله قبلاً حل شده یا نه؛ اگر جواب آن را داشتیم، می‌توانیم آن را مستقیماً استفاده کنیم؛ در غیر این صورت، زیرمسئله را حل می‌کنیم و جواب آن را به جدول اضافه می‌کنیم. در این رویکرد مسئله به زیرمسئله‌هایی شکسته می‌شود و پاسخ هر زیرمسئله پس از محاسبه در جایی ذخیره می‌شود. در مراحل بعدی هر وقت به آن پاسخ نیاز بود پاسخ از روی حافظه خوانده می‌شود. این فرایند ترکیبی از الگوریتم بازگشتی و ذخیره‌سازی در حافظه است.
رویکرد پایین به بالا: پس از آن که جواب یک مسئله را به صورت بازگشتی با استفاده از زیرمسئله‌های آن صورت‌بندی کردیم، می‌توانیم مسئله را از پایین به بالا نگاه کنیم: ابتدا زیرمسئله‌ها را حل می‌کنیم و سپس جواب آن‌ها را برای به دست آوردن جواب زیرمسئله‌های بزرگ‌تر استفاده می‌کنیم تا نهایتاً به مسئلهٔ اصلی برسیم. این روش نیز معمولاً به کمک یک جدول با تولید مرحله به مرحلهٔ زیرمسئله‌های بزرگ‌تر و بزرگ‌تر به کمک جواب زیرمسئله‌های کوچک‌تر انجام می‌شود؛ برای مثال، اگر مقادیر F41 و F40 را بدانیم، می‌توانیم مستقیماً مقدار F42 را به دست آوریم. در این رویکرد همهٔ زیرمسئله‌های مورد نیاز از کوچک به بزرگ حل می‌شوند و از جواب‌ها «بلافاصله» برای محاسبهٔ بعدی‌ها استفاده می‌شود و فرایند محاسبه تا رسیدن به زیرمسئلهٔ مورد نیاز (که در واقع مسئلهٔ اصلی ماست) ادامه می‌یابد. بدیهی است که در این حالت استفاده از الگوریتم بازگشتی ضروری نیست. مثال زیر این تفاوت‌ها را روشن‌تر می‌کند. برخی از زبان‌های برنامه‌نویسی می‌توانند به‌طور خودکار جواب صدا زدن یک تابع با ورودی‌های مشخص را به خاطر بسپارند تا صدا زدن با نام را سرعت ببخشند (این فرایند با نام صدا زدن با نیاز شناخته‌می‌شود). برخی زبان‌ها به شکل سیار این امکان را در اختیار برنامه‌نویس قرار می‌دهند (مانند Scheme ,Common Lisp ,Perl و D). برخی زبان‌های نیز به صورت خودکار به‌خاطرسپاری را در خود دارند: مانند Prolog جدول‌دار و J، که به‌خاطرسپاری را با قید .M پشتیبانی می‌کند. در هر صورت، این تنها برای یک تابع با شفافیت ارجاعی امکان دارد. به‌خاطرسپاری به عنوان یک الگوی طراحی در دسترس نیز در زبان‌های بازنویسی جملات مانند زبان ولفرام یافت‌می‌شود.