stanford-oval/wikipedia huggingface dataset:
درسویانکا

| درسویانکا Дресвянка | درسویانکا Дресвянка |
| --- | --- |
Selo: Selo
درسویانکانمایش نقشه Altai Kraiدرسویانکانمایش نقشه روسیه: درسویانکانمایش نقشه Altai Kraiدرسویانکانمایش نقشه روسیه
مختصات: ۵۳°۵۲′ شمالی ۸۱°۲۰′ شرقی﻿ / ﻿۵۳٫۸۶۷°شمالی ۸۱٫۳۳۳°شرقی﻿ / 53.867; 81.333: مختصات: ۵۳°۵۲′ شمالی ۸۱°۲۰′ شرقی﻿ / ﻿۵۳٫۸۶۷°شمالی ۸۱٫۳۳۳°شرقی﻿ / 53.867; 81.333
کشور: روسیه
ناحیه‌های فدرال روسیه: سرزمین آلتای
شهر: شهرستان کامنسکی (سرزمین آلتای)
منطقهٔ زمانی: یوتی‌سی +۷:۰۰
درسویانکا (به لاتین: Dresvyanka) یک منطقهٔ مسکونی در روسیه است که در سرزمین آلتای واقع شده‌است.
دبوریه

| دبوریه דַבּוּרִיָּה, דבורייה‎ دبورية‎> نویسه‌گردانی(های) عبری | دبوریه דַבּוּרִיָּה, דבורייה‎ دبورية‎> نویسه‌گردانی(های) عبری |
| --- | --- |
 • ISO 259: Dabburiya
 • تلفظ دیگر: Deburieh (unofficial)
دبوریه: دبوریه
مختصات: ۳۲°۴۱′۳۱″ شمالی ۳۵°۲۲′۱۸″ شرقی﻿ / ﻿۳۲٫۶۹۱۹۴°شمالی ۳۵٫۳۷۱۶۷°شرقی﻿ / 32.69194; 35.37167: مختصات: ۳۲°۴۱′۳۱″ شمالی ۳۵°۲۲′۱۸″ شرقی﻿ / ﻿۳۲٫۶۹۱۹۴°شمالی ۳۵٫۳۷۱۶۷°شرقی﻿ / 32.69194; 35.37167
Grid position: 185/232 PAL
استان: استان شمال
حکومت: حکومت
 • نوع: Local council (از 1961)
مساحت: مساحت
 • کل: ۷۲۰۰ دونوم (۷٫۲ کیلومتر مربع یا ۲٫۸ مایل مربع)
جمعیت (۲۰۱۷): جمعیت (۲۰۱۷)
 • کل: ۱۰٬۱۵۴
دبوریه (به لاتین: Daburiyya) یک منطقهٔ مسکونی در اسرائیل است که در شمال واقع شده‌است.
درسی از سینمای لهستان

| درسی از سینمای لهستان | درسی از سینمای لهستان |
| --- | --- |
کارگردان: آندری وایدا
فیلمنامه‌نویس: آندری وایدا  رافائو مارشائوئِک
فیلم‌بردار: کشیشتف توشیویچ   آندژی وُلف
تدوین‌گر: کاتاژینا رودنیک
تاریخ‌های انتشار: ۲۰۰۲
مدت زمان: ۷۱ دقیقه
کشور: لهستان
زبان: لهستانی 
درسی از سینمای لهستان (لهستانی: Lekcja polskiego kina) با نام کاملِ آندری وایدا روایت می‌کند: چگونه مکتب فیلم لهستان بنیان نهاده شد (لهستانی: Jak powstała polska szkoła filmowa - opowiada Andrzej Wajda) یک فیلم مستند لهستانی به کارگردانی آندری وایدا است که در سال ۲۰۰۲ منتشر شد.
دامفریشر

| دامفریشر | دامفریشر |
| --- | --- |
شایر: شایر
کشور: اسکاتلند
مرکز: دامفریس
مساحت: مساحت
 • کل: ۱۰۶۳ مایل مربع (۲٬۷۵۳ کیلومتر مربع)
 : Ranked 8th of 34
Chapman code: DFS
دامفریشر (به انگلیسی: Dumfriesshire) یک منطقهٔ مسکونی در اسکاتلند است که در دامفریس و گالووی واقع شده‌است.
خنگ کمال‌وند

| خنگ کمال‌وند | خنگ کمال‌وند |
| --- | --- |
روستا: روستا
مختصات: ۳۱°۵۶′۳۲″شمالی ۴۹°۴۹′۵۹″شرقی﻿ / ﻿۳۱٫۹۴۲۲۰۴°شمالی ۴۹٫۸۳۳۱۴۱°شرقی﻿ / 31.942204; 49.833141: مختصات: ۳۱°۵۶′۳۲″شمالی ۴۹°۴۹′۵۹″شرقی﻿ / ﻿۳۱٫۹۴۲۲۰۴°شمالی ۴۹٫۸۳۳۱۴۱°شرقی﻿ / 31.942204; 49.833141
کشور: ایران
استان: خوزستان
شهرستان: ایذه
بخش: بخش مرکزی
دهستان: حومه غربی
جمعیت: ۵۲۹ نفر
خنگ کمال‌وند، روستایی از توابع بخش مرکزی شهرستان ایذه در استان خوزستان ایران است.
جمعیت

این روستا در دهستان حومه‌غربی قرار دارد و براساس سرشماری مرکز آمار ایران در سال ۱۳۸۵، جمعیت آن ۵۲۹ نفر (۸۴خانوار) بوده‌است.
دامفلت

| دامفلت   | دامفلت   |
| --- | --- |
  نشان:   نشان
کشور: آلمان
ایالت: شلسویگ-هولشتاین
ناحیه: Steinburg
انجمن شهرداری: Wilstermarsch
حکومت: حکومت
 • شهردار: Delf Sievers
مساحت: مساحت
 • کل: ۱۶٫۱۱ کیلومتر مربع (۶٫۲۲ مایل مربع)
ارتفاع: ۰ متر (۰ فوت)
جمعیت (۲۰۰۶-۱۲-۳۱): جمعیت (۲۰۰۶-۱۲-۳۱)
 • کل: ۳۳۰
 • تراکم: ۲۰/کیلومتر مربع (۵۳/مایل مربع)
منطقهٔ زمانی: CET/CEST (UTC+1/+2)
کدهای پستی: ۲۵۵۵۴
کدهای شماره‌گیری: ۰۴۸۲۳
پلاک خودرو: IZ
وبگاه: www.wilstermarsch.de
دامفلت (به آلمانی: Dammfleth) یک شهر در آلمان است که در اشتاینبورگ واقع شده‌است. دامفلت ۳۳۰ نفر جمعیت دارد.
جرم کمار

جرم کمار (به انگلیسی: Komar mass) (برگرفته از نام آرتور کمار)، یک سیستم یکی از چندین مفهوم صوری جرم است که در نسبیت عام به کار می رود. جرم کمار را می توان در هر فضازمان ساکنی تعریف نمود. در فضازمان ساکن همه متریک هارا می توان به گونه ای نوشت که مستقل از زمان باشند. به طور معادل فضازمان ساکن را می توان به صورت فضازمانی تعریف نمود که دارای یک میدان برداری کیلینگ می باشد.
پیز روزاتس

| پیز روزاتس | پیز روزاتس |
| --- | --- |
fa (in English: Expected satiety): fa
پیز روزاتسموقعیت پیز روزاتس در نقشه : پیز روزاتسموقعیت پیز روزاتس در نقشه 
مرتفع‌ترین نقطه: مرتفع‌ترین نقطه
ارتفاع: ۳٬۱۲۳ متر (۱۰٬۲۴۶ فوت)
برجستگی: ۲۸ متر (۹۲ فوت)
قله مادر: Piz Surlej
مختصات: ۴۶°۲۷′۳۶٫۳″ شمالی ۹°۵۱′۱۳″ شرقی﻿ / ﻿۴۶٫۴۶۰۰۸۳°شمالی ۹٫۸۵۳۶۱°شرقی﻿ / 46.460083; 9.85361
جغرافیا: جغرافیا
موقعیت: کانتون گراوبوندن، سوئیس
رشته‌کوه مادر: رشته‌کوه برنینا
پیز روزاتس (به لاتین: Piz Rosatsch) یک کوه در سوئیس است که در کانتون گراوبوندن واقع شده‌است. پیز روزاتس ۳٬۱۲۳ متر بالاتر از سطح دریا واقع شده‌است.
تپه علی میرزا

| تپه علی میرزا (ثبت توسط:عارف غفاری) | تپه علی میرزا (ثبت توسط:عارف غفاری) |
| --- | --- |
نام: تپه علی میرزا (ثبت توسط:عارف غفاری)
کشور: ایران
استان: استان اردبیل
شهرستان: شهرستان مشگین‌شهر
بخش: مشگین شرقی
اطلاعات اثر: اطلاعات اثر
نام محلی: روستای میرعلیلو
نام‌های دیگر: ماشالله تپه سی
نوع بنا: تپه
کاربری: تپه
دیرینگی: دوران پیش از تاریخ ایران باستان
دورهٔ ساخت اثر: دوران پیش از تاریخ ایران باستان
بانی اثر: عارف غفاری
اطلاعات ثبتی: اطلاعات ثبتی
شمارهٔ ثبت: ۶۲۰
تاریخ ثبت ملی: ۲۵ اسفند ۱۳۴۵
اطلاعات بازدید: اطلاعات بازدید
امکان بازدید: عید نوروز هر سال
تپه علی میرزا مربوط به دوران پیش از تاریخ ایران باستان است و در شهرستان مشگین‌شهر، روستای میرعلیلو واقع شده و این اثر در تاریخ ۲۵ اسفند ۱۳۴۵ با شمارهٔ ثبت ۶۲۰ به‌عنوان یکی از آثار ملی ایران به ثبت رسیده‌است.
میدوی، شهرستان روآن، تنسی

| میدوی، شهرستان روآن، تنسی | میدوی، شهرستان روآن، تنسی |
| --- | --- |
محدوده ثبت‌نشده: محدوده ثبت‌نشده
میدوی، شهرستان روآن، تنسیموقعیت میدوی، شهرستان روآن، تنسی در نقشهنمایش نقشه تنسیمیدوی، شهرستان روآن، تنسیمیدوی، شهرستان روآن، تنسی (ایالات متحده آمریکا)نمایش نقشه ایالات متحده آمریکا: میدوی، شهرستان روآن، تنسیموقعیت میدوی، شهرستان روآن، تنسی در نقشهنمایش نقشه تنسیمیدوی، شهرستان روآن، تنسیمیدوی، شهرستان روآن، تنسی (ایالات متحده آمریکا)نمایش نقشه ایالات متحده آمریکا
مختصات: ۳۵°۴۶′۳۴″ شمالی ۸۴°۳۳′۰۶″ غربی﻿ / ﻿۳۵٫۷۷۶۱۱°شمالی ۸۴٫۵۵۱۶۷°غربی﻿ / 35.77611; -84.55167: مختصات: ۳۵°۴۶′۳۴″ شمالی ۸۴°۳۳′۰۶″ غربی﻿ / ﻿۳۵٫۷۷۶۱۱°شمالی ۸۴٫۵۵۱۶۷°غربی﻿ / 35.77611; -84.55167
کشور:  ایالات متحده آمریکا
ایالت: تنسی
شهرستان: شهرستان روان، تنسی
ارتفاع: ۲۶۰ متر (۸۶۰ فوت)
منطقهٔ زمانی: یوتی‌سی -۵ (منطقه زمانی شرقی)
 • تابستانی (DST): یوتی‌سی -۴ (EDT)
کد منطقه: 865
شماره GNIS: ۱۳۱۵۴۹۹
میدوی (به انگلیسی: Midway) یک منطقهٔ مسکونی در ایالات متحده آمریکا است که در شهرستان روان، تنسی واقع شده‌است. میدوی ۲۶۲٫۱۳ متر بالاتر از سطح دریا واقع شده‌است.
برنامه‌نویسی پویا

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

این روش در سال ۱۹۵۳ توسط ریاضی‌دانی به نام ریچارد بلمن معرفی شد. برنامه‌ریزِی پویا در ریاضی و علوم رایانه روشی شناخته شده‌است که از آن در نوشتن الگوریتم‌های بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده می‌شود. تعریف برنامه‌ریزی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده‌است که روش علوم رایانه‌ای برای برنامه‌ریزی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می‌کند در حالی که در روش ریاضی برنامه‌ریزی پویا امکان کاهش فضای حافظه بیشتر است.
برنامه‌ریزی پویا شبیه روش تقسیم و حل، مسائل را با استفاده از ترکیب کردن جواب زیرمسئله‌ها حل می‌کند. الگوریتم تقسیم و حل، مسئله را به زیر مسئله‌های مستقل تقسیم می‌کند و پس از حل زیر مسئله‌ها به صورت بازگشتی، نتایج را با هم ترکیب کرده و جواب مسئله اصلی را به‌دست می‌آورد. به عبارت دقیق تر، برنامه‌ریزی پویا بهتر است در مسائلی استفاده شود که زیرمسئله‌ها مستقل نیستند؛ یعنی زمانی که زیرمسئله‌ها، خود دارای چندین زیر مسئلهٔ یکسان هستند. در این حالت روش تقسیم و حل با اجرای مکرر زیرمسئله‌های یکسان، بیشتر از میزان لازم محاسبات انجام می‌دهد. یک الگوریتم برنامه‌ریزی پویا زیرمسئله‌ها را یک بار حل و جواب آن‌ها را در یک جدول ذخیره می‌کند و با این کار از تکرار اجرای زیرمسئله‌ها در زمانی که مجدداً به جواب آن‌ها نیاز است جلوگیری می‌کند. مثلا اگر مسئله فیبوناچی با برنامه ریزی پویا حل شود باعث اجرای مکرر یک زیرمسئله نمی شود. مثلا برای محاسبه f(5) مقادیر f(4) و f(3) تنها یک بار محاسبه می شوند. ولی اگر از روش تقسیم و حل استفاده شود. f(3) دو بار محاسبه می شود که سربار محاسباتی است.
ویژگی‌ها

یک مسئله باید دارای دو مشخصهٔ کلیدی باشد تا بتوان برنامه‌نویسی پویا را برای آن به کار برد: زیرساختار بهینه و زیرمسئله‌های هم‌پوشان. در طرف مقابل، به حل یک مسئله با ترکیب جواب‌های بهینهٔ زیرمسئله‌های ناهم‌پوشان، «تقسیم و حل» گفته‌می‌شود. به همین علت است که مرتب‌سازی ادغامی و سریع به عنوان مسائل برنامه‌نویسی پویا شناخته‌نمی‌شوند.
ویژگی‌ها > اصل بهینگی

اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله‌ها را ایجاب می‌کند.
پس می‌توان از روش برنامه‌نویسی پویا استفاده کرد.
حل بهینه، سومین مرحله از بسط یک الگوریتم برنامه‌نویسی پویا برای مسائل بهینه‌سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:
ارائه یک ویژگی بازگشتی که حل بهینهٔ نمونه‌ای از مسئله را به دست می‌دهد.
محاسبه مقدار حل بهینه به شیوهٔ جزء به کل.
بنا کردن یک حل نمونه به شیوهٔ جزء به کل.
تمام مسائل بهینه‌سازی را نمی‌توان با برنامه‌نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.
اصل بهینگی در یک مسئله صدق می‌کند اگر یک حل بهینه برای نمونه ای از مسئله، همواره حاوی حل بهینه برای همهٔ زیر نمونه‌ها باشد.
در روش برنامه‌نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیرمسائل به صورت جزء به کل حل می‌شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده‌اند محاسبه می‌شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده‌اند محاسبه می‌شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می‌شوند که قبلاً محاسبات آن‌ها صورت گرفته، و نتایج آن‌ها در آرایه ذخیره شده‌اند. در نتیجه نیاز به محاسبه مجدد آن‌ها نیست. به همین ترتیب در مرحله بعد زیرمسائل با چهار ماتریس محاسبه می‌شوند، و الی آخر.
درختهای جستجوی دودویی بهینه
درخت جستجوی دودویی یک درخت دودویی از عناصر است که معمولاً کلید نامیده می‌شوند به قسمی که:
هر گره حاوی یک کلید است.
کلیدهای موجود در زیردرخت چپ هر گره، کوچکتر یا مساوی کلید آن گره هستند.
کلیدهای موجود در زیردرخت راست هر گره، بزرگتر یا مساوی کلید آن گره هستند
ویژگی‌ها > زیرسازه بهینه

زیرساختار بهینه به این معناست که جواب یک مسئلهٔ بهینه‌سازی را بتوان از ترکیب جواب‌های بهینهٔ زیرمسئله‌های آن به دست آورد. چنین زیرساختارهای بهینه‌ای معمولاً با رویکرد بازگشتی به دست می‌آیند؛ برای مثال، در گراف (G=(V,E، کوتاه‌ترین مسیرِ م از رأس آ به رأس ب، زیرساختار بهینه از خود نشان می‌دهد: هر رأس میانیِ ث از مسیرِ م را در نظر بگیرید. اگر م واقعاً کوتاه‌ترین مسیر باشد، آنگاه می‌توان آن را به دو زیرمسیر م۱ از آ تا ث و م۲ از ث تا ب در نظر گرفت، به نحوی که هر کدام از این‌ها کوتاه‌ترین مسیر بین دو سر خود هستند (به همان طریق برش و چسباندن کتاب مقدمه‌ای بر الگوریتم‌ها). بر این اساس، می‌توان جواب را به صورت بازگشتی بیان کرد، درست مانند الگوریتم‌های بلمن-فورد و فلوید-وارشال.
استفاده از روش زیرسازه بهینه به این معناست که مسئله را به زیرمسئله‌هایی کوچک‌تر بشکنیم و برای هر یک از این زیرمسئله‌ها پاسخی بهینه بیابیم و پاسخ بهینه مسئلهٔ کلی را از کنار هم قرار دادن این پاسخ‌های بهینهٔ جزئی به دست آوریم. مثلاً در هنگام حل مسئلهٔ یافتن کوتاه‌ترین مسیر از یک رأس یک گراف به رأسی دیگر، می‌توانیم کوتاه‌ترین مسیر تا مقصد از همهٔ رئوس مجاور را به دست آوریم و از آن برای جواب کلی استفاده کنیم. به‌طور کلی حل مسئله از این روش شامل سه مرحله است.
شکستن مسئله به بخش‌های کوچک‌تر
حل خود این زیرمسئله‌ها با شکاندن آن‌ها به صورت بازگشتی
استفاده از پاسخ‌های جزئی برای یافتن پاسخ کلی
گراف زیرمسئله‌ها

زمانی که به یک مسئلهٔ برنامه‌نویسی پویا می‌اندیشیم، باید مجموعهٔ زیرمسئله‌های موجود و چگونگی وابستگی آن‌ها را درک کنیم.
گراف زیرمسئله‌ها دقیقاً همین اطلاعات را برای یک مسئله در بر می‌گیرد. تصویر ۱ گراف زیرمسئله‌های دنباله‌های فیبوناچی را نشان می‌دهد. گراف زیرمسئله‌ها یک گراف جهت‌دار، شامل یک رأس به ازای هر زیرمسئلهٔ متمایز است و در صورتی یک یال جهت‌دار از رأس زیرمسئلهٔ x به رأس زیرمسئلهٔ y دارد که برای تعیین یک جواب بهینه برای زیرمسئلهٔ x مستقیماً نیاز به در نظر گرفتن یک جواب بهینه برای زیرمسئلهٔ y داشته‌باشیم. برای نمونه، گراف زیرمسئله دارای یک یال از x به y است، در صورتی که یک رویهٔ (procedure) بازگشتی بالا به پایین برای حل x، مستقیماً خود را برای حل y صدا بزند. می‌توان گراف زیرمسئله‌ها را یک نسخهٔ کاهش‌یافتهٔ درخت بازگشتی برای روش بازگشتی بالا به پایین در نظر گرفت، به گونه‌ای که همهٔ رئوس مربوط به یک زیرمسئله را یکی کنیم و یال‌ها را از والد به فرزند جهت‌دار کنیم.
روش پایین به بالا برای برنامه‌نویسی پویا رئوس گراف زیرمسئله‌ها را به ترتیبی در نظر می‌گیرد که همهٔ زیرمسئله‌های مجاور یک زیرمسئله، پیش از آن حل شوند. در یک الگوریتم برنامه‌نویسی پویای پایین به بالا، رئوس گراف زیرمسئله‌ها را به صورتی در نظر می‌گیریم که «معکوس مرتب توپولوژیکی» یا «مرتب توپولوژیک وارون» زیرگراف مسئه‌ها است. به زبان دیگر، هیچ زیرمسئله‌ای تا زمانی که همهٔ زیرمسئله‌هایی که به آن‌ها وابسته است حل نشده‌اند، در نظر گرفته‌نمی‌شود. به‌طور مشابه، می‌توانیم رویکرد بالا به پایین (همراه به‌خاطرسپاری) برای برنامه‌نویسی پویا را به شکل جستجوی ژرفانخست گراف زیرمسئله‌ها ببینیم.
اندازهٔ گراف زیرمسئله‌ها می‌تواند ما را در تعیین زمان اجرای الگوریتم برنامه‌نویسی پویا یاری کند. از آنجایی که هر زیرمسئله را فقط یک بار حل می‌کنیم، زمان اجرا برابر است با مجموع تعداد بارهایی که نیاز است هر زیرمسئله را حل کنیم. به‌طور معمول، زمان محاسبهٔ جواب یک زیرمسئله، متناسب با درجهٔ رأس متناظر در گراف، و تعداد زیرمسئله‌ها برابر با تعداد رئوس گراف است.
مثال

یک پیاده‌سازی ساده از یک تابع برای یافتن عدد فیبوناچی nام می‌تواند به شکل زیر باشد.
function fib(n)
    if n = 0    
        return 0        
    if n = 1    
        return 1        
    return fib(n − 1) + fib(n − 2)
برای مثال اگر از چنین تابعی (fib(5 را بخواهیم، تابع‌هایی که صدا می‌شوند به شکل زیر خواهند بود.
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
مشخص است که چنین فرایندی پر از محاسبات تکراری است. مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب شده‌است. در محاسبات بزرگ‌تر چنین تکرارهایی برنامه را به شدت کند می‌کنند. این الگوریتم دارای پیچیدگی زمانی نمایی است.
حال فرض کنید ما یک آرایه دوتایی map داریم که عدد n را به مقدار عدد فیبوناچی nام مربوط کرده و ذخیره می‌کند. پیچیدگی زمانی چنین الگوریتمی n خواهد بود. همچنین میزان فضای اشغال‌شده‌اش هم از مرتبه n خواهد بود.
var m := map(0 → 1, 1 → 1)
function fib(n)
    if map m does not contain key n
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]
این نمونه‌ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکستیم و بعد به محاسبه و ذخیرهٔ پاسخ زیرمسئله‌ها پرداختیم.
در فرایند پایین به بالا برای حل چنین مسئله‌ای از عدد فیبوناچی یکم شروع می‌کنیم تا به عدد خواسته‌شده برسیم. با این کار باز هم پیچیدگی زمانی از مرتبه n است.
function fib(n)
     var previousFib := 0, currentFib := 1
     if n = 0
         return 0
     if n = 1
         return 1
     repeat n − 1 times
         var newFib := previousFib + currentFib
         previousFib := currentFib
         currentFib := newFib
     return currentFib
برتری این روش به روش قبلی در این است که در این روش حتی به فضای ذخیره از مرتبه n هم نیازی نیست. فضای ذخیره از مرتبه ۱ کفایت می‌کند. علت این که همیشه از رویکرد پایین به بالا استفاده نمی‌کنیم این است که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم.
تفاوت این روش و روش تقسیم و غلبه (تقسیم و حل)

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.
زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:
داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملاً مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجهٔ حاصل از آن بخش، اثری ندارند. معمولاً روش تقسیم و حل برای چنین مسائلی کارایی خوبی دارد.
داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است.
روش برنامه‌نویسی پویا غالباً برای الگوریتم‌هایی به کار برده می‌شود که در پی حل مسئله‌ای به صورت بهینه می‌باشند.
در روش تقسیم و غلبه ممکن است برخی از زیرمسائلِ کوچکتر، با هم برابر باشند که در این صورت زیرمسائلِ برابر، به‌طور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و غلبه است.
ایده‌ای که در فرایِ روش برنامه‌نویسی پویا نهفته‌است، جلوگیری از انجام این محاسبات تکراری است و روشی که معمولاً برای این عمل به کارگرفته می‌شود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر الگوریتم به زیرمسئله‌ای برخورد کرد که پیش از این حل شده است، به جای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال می‌کند.
روش برنامه‌نویسی پویا یک روش پایین به بالا است (البته همان‌طور که گفته شد، اگر از قبل بدانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبور نباشیم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم) به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. درحالی‌که از نظر ساختاری، روش تقسیم و غلبه روشی است از بالا به پایین، یعنی به‌طور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و به سمت پایین و حل مسائلِ کوچکتر، به پیش می‌رود.
مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر

ما بیشتر و بیشتر می‌بینیم که مسائل مربوط به برنامه‌ریزی منبع خیلی خوبی از مسایل الگوریتمی را با انگیزهٔ عملی ارائه می‌دهد. تاکنون مشکلاتی را در نظر گرفتیم که در آن درخواست‌ها با فاصلهٔ زمانی مشخص از یک منبع مشخص‌شده و همچنین مشکلاتی که در آن درخواست‌ها دارای مدت و مهلت هستند، اما فواصل خاصی را که در طی آن باید انجام شود تعیین نشده‌است. در این بخش، ما نسخه‌ای از نوع دوم مشکل را با مدت زمان و مهلت در نظر می‌گیریم، که حل مستقیم با استفاده از تکنیک‌هایی که تاکنون دیده‌ایم، دشوار است.
ما برای حل مسئله از برنامه‌نویسی پویا استفاده خواهیم کرد، اما با یک تغییر: مشخص می‌شود مجموعه زیرمسئله‌ها به اندازه کافی نخواهدبود، و بنابراین ما در نهایت به ایجاد یک مجموعه غنی‌تر از زیرمسئله‌ها می‌پردازیم. همان‌طور که خواهیم‌دید، این کار با اضافه کردن یک متغیر جدید به بازگشت در زیربرنامهٔ پویا انجام می‌شود.
مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر > مسئله

در مسئلهٔ برنامه‌ریزی که در اینجا مورد توجه قرار می‌دهیم، ما یک ماشین داریم که می‌تواند دستورها را پردازش کند همچنین یک سری درخواست‌ها  1,2,\ldots ,n داریم که می‌توانیم از آن در بازهٔ زمانی  0 تا  W استفاده کنیم. هر درخواست مربوط به یک دستور است که برای پردازش آن به  w_{i} واحد زمانی نیاز داریم. اگر هدف ما این باشد که دستورها را پردازش کنیم به طوری که ماشین را تا زمان  W مشغول نگه داریم، کدام دستورها را باید انتخاب کنیم؟
به زبان دقیق تر، فرض کنید که ما آیتم‌های  1,2,\ldots ,n را داریم، که هر کدام دارای وزن  w_{i} است. هدف ما انتخاب یک زیرمجموعه از این آیتم‌ها است به طوری که مجموع  w_{i}های آیتم‌های انتخاب شده از  W کمتر مساوی باشند و با توجه به این محدودیت، مجموع این وزن‌ها بیشترین مقدار ممکن باشد. ما این مسئله را «مسئلهٔ مجموع زیرمجموعه» می‌نامیم.
این مسئله یک حالت خاص رایج از مسئلهٔ کوله پشتی است، که هر درخواست  i یک ارزش  v_{i} و یک‌وزن  w_{i} دارد. هدف در این مسئلهٔ کلی‌تر این است که زیرمجموعه‌ای با بیشترین مجموع ارزش انتخاب کنیم با توجه به اینکه نباید مجموع وزن‌ها از  W بیشتر باشد. به‌طور معمول مسئلهٔ کوله پشتی یک زیرمسئله از مسائل کلی‌تر است. نام «کوله پشی» اشاره به مسئلهٔ پر کردن یک کوله پشتی با ظرفیت  W دارد که باید آن را تا جای ممکن با استفاده از مجموعه ای از آیتم‌ها پرکرد. ما از واژهٔ وزن یا زمان برای اشاره به  W،  w_{i} استفاده خواهیم کرد.
چون این مسئله، مسائل برنامه‌ریزی دیگری که قبلاً دیده‌ایم را شبیه‌سازی می‌کند، طبیعی است که از خود بپرسیم آیا الگوریتم حریصانه‌ای برای راه‌حل بهینه وجود دارد یا خیر. به نظر می‌آید که پاسخ خیر باشد، حداقل تا کنون هیچ روش حریصانهٔ کارایی شناخته نشده‌است که آیتم‌ها را به صورت نزولی مرتب کند؛ یا حداقل این کار را برای آیتم‌های با وزن حداکثر  W انجام دهد، و سپس ما شروع به انتخاب آیتم‌ها با این ترتیب کنیم تا جایی که مجموع وزن آیتم‌های انتخاب شده کمتر از  W باشد. اما اگر  W مضرب دو باشد، و ما سه آیتم با وزن‌های  \{{\frac {w}{2}},{\frac {w}{2}},{\frac {w}{2}}+1\} داشته‌باشیم، خواهیم دید که الگوریتم حریصانه جواب بهینه را تولید نخواهد کرد. به‌طور جایگزین می‌توانستیم آیتم‌ها را بر اساس وزنشان به صورت صعودی مرتب کنیم و کار مشابه را انجام دهیم، ولی این بار در ورودی‌های  \{{\frac {w}{2}},{\frac {w}{2}},1\} شکست می‌خورد.
هدف ما این است که نشان دهیم که چگونه با استفاده از برنامه‌نویسی پویا این مسئله را حل کنیم. اصول اولیهٔ برنامه‌نویسی پویا را به یاد بیاورید: ما باید تعداد کمی از زیرمسئله‌ها را داشته باشیم به طوری که هر زیرمسئله را بتوان به راحتی با استفاده از زیرمسئله‌های «کوچکتر» حل کرد و پاسخ به مسئلهٔ اصلی به‌راحتی به‌دست می‌آید، هنگامی که ما پاسخ همهٔ زیر مسئله‌ها را بدانیم.
مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر > طراحی الگوریتم

می‌خواهیم از تعداد زیادی زیرمسئله استفاده کنیم. در واقع برای هر مجموعهٔ اولیه  \{1,\ldots ,i\} از آیتم‌ها و هر مقدار ممکن w برای بیشینه وزن ممکن، زیرمسئله‌ای در نظر می‌گیریم تا با استفاده از آنها بتوانیم سریعتر مسئله را حل کنیم. فرض کنید که  W یک عدد صحیح باشد و همهٔ درخواست‌های  i=1,2,\ldots ,n مقادیر صحیح  w_{i} هستند. ما یک زیرمسئله به ازای هر  i=1,2,\ldots ,n و هر  w\leq W داریم. ما  opt(i,w) را به عنوان مقدار پاسخ بهینه برای آیتم‌های  1,2,\ldots ,i و بیشینه وزن مجاز  w تعریف می‌کینم که برابر است با:
opt(i,w)=\max _{s}\Sigma _{s}w_{j}
که  \max  روی زیرمجموعهٔ  s\in \{1,\ldots ,i\} است که  w_{i}\leq W را ارضا می‌کند. استفاده از این مجموعهٔ جدید از زیرمسئله‌ها، این اجازه را به ما می‌دهد که مقدار  opt(i,w) به عنوان یک عبارت ساده بر حسب مقادیر به‌دست آمده از مسائل کوچکتر بیان کرد. علاوه بر این  opt(i,w) کمیتی است که ما در انتها به دنبال آن هستیم. فرض کنید که o نمایانگر راه‌حل بهینه برای مسئلهٔ اصلی باشد. دو حالت داریم:
۱- اگر  n\notin o آنگاه  opt(n,W)=opt(n-1,W) پس به راحتی می‌توانیم عبارت  n را نادیده بگیریم.
۲- اگر  n\in o آنگاه  opt(n,W)=w_{n}+opt(n-1,W-w_{n})، از این به بعد ما به دنبال استفاده از ظرفیت باقی‌ماندهٔ  W-w_{n} هستیم.
هنگامی که آیتم nام بسیار بزرگ است،  w_{n}>W ما باید داشته باشیم  opt(n,W)=opt(n-1,W). در غیر این صورت، ما راه‌حل بهینه را از این طریق با توجه به اینکه برای هر n درخواست کدام یک از گزینه‌های بالا بهتر است به‌دست می‌آوریم. با استفاده از استدلال مشابه برای زیرمسئلهٔ آیتم‌های  \{1,\ldots ,i\} و بیشینه وزن  w، رابطهٔ بازگشتی روبرو را می‌دهد:
(*)
اگر  w_{i}>W آنگاه opt(i,W)=opt(i-1,W). در غیر اینصورت: opt(i,w)=\max\{opt(i-1,w),w_{i}+opt(i-1,w-w_{i})\}
مانند قبل، ما می‌خواهیم الگوریتمی طراحی کنیم که جدولی از همهٔ مقادیر ممکن  opt(i,w) داشته باشیم درحالی که هر کدام از آنها را حداکثر یکبار محاسبه کرده باشیم.
با استفاده از لم (*) می‌توان فوراً ثابت کرد که مقدار برگشتی  M[n,W] برای در خواست‌های  1,2,\ldots ,n و وزن در دسترس  W، پاسخ بهینه‌ای است .( M یک آرایهٔ دو بعدی است که مقادیر  opt(i,w) را در خود ذخیره کرده‌است)
مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر > آنالیز آلگوریتم

برای الگوریتمی که در این شرایط طراحی کرده‌ایم، اما به یک جدول دو بعدی نیاز داریم، که بازتاب دو بعدی جدول زیرسوالات است که در حال ساخته شدن هستند. به عنوان یک مثال از اجرای این الگوریتم، به یک نمونه با وزن  W=6 و  n=3 و آیتم‌هایی با اندازه  w_{1}=w_{2}=2 و  w_{3}=3 توجه کنید. ما در خواهیم یافت که مقدار بهینه  opt(3,6)=6 خواهدبود (که با استفاده از سومین آیتم و یکی از دو آیتم اول آن را به‌دست آورده‌ایم).
قبل از آن، در مورد برنامه‌ریزی فواصل زمانی موزون، جدول راه حل‌های  M را ساخته‌ایم، و مقادیر  M[i,W] را با استفاده از مقادیر قبلی در زمان اجرای  {\mathcal {O}}(1)محاسبه می‌کنیم؛ بنابراین مدت زمان اجرا متناسب با تعداد ورودی‌ها به جدول می‌باشد.
(**)
الگوریتم مجموع زیرمجموعه  (n,w) بهینه جواب مسئله را محاسبه می‌کند و زمان اجرای آن  {\mathcal {O}}(nw) است.
توجه کنید که زمان اجرای برنامه تابعی از چندجمله‌ای بر حسب n نیست، در واقع یک تابع چندجمله ای از  n و  w است. ما چنین الگوریتم‌هایی را «شبه چندجمله‌ای» می‌نامیم. الگوریتم‌های شبه‌چندجمله‌ای می‌توانند به‌طور قابل توجهی کارا باشند هنگامی که اعداد  \{w_{i}\}ی که به عنوان ورودی دریافت می‌کنیم به‌طور قابل توجهی کوچک باشند. هرچند هنگامی که  {w_{i}}ها بزرگ می‌شوند عملکرد این الگوریتم‌ها کاهش می‌یابد.
برای به‌دست آوردن یک مجموعه بهینه  s از آیتم‌ها، می‌توانیم آرایهٔ  M را با استفاده از روشی که در قبل گفته شد ردیابی کنیم.
(***)
یک جدول  M از بهینه مقدارهای زیرمسئله‌ها داده شده‌است. بهترین مجموعه  s را می‌توان در زمان  {\mathcal {O}}(n) پیدا کرد.