افراز عدد صحیح
می‌شمارد n به چند طریق جمع عددهای مثبت می‌شود (ترتیب مهم نیست)؛ با برنامه‌ریزی پویا، قسمت‌ها یکی‌یکی مجاز می‌شوند.
افراز عدد n یعنی نوشتنش به صورت جمع عددهای مثبت، بدون توجه به ترتیب: ۴ = ۳ + ۱ = ۲ + ۲ = ۲ + ۱ + ۱ = ۱ + ۱ + ۱ + ۱ (پنج افراز).
- زمان:
O(n²) - حافظه:
O(n) - گریمالدی، فصل ۹
- هوروویتز–ساهنی، فصل ۵
p(5) = 7: ۵، ۴+۱، ۳+۲، ۳+۱+۱، ۲+۲+۱، ۲+۱+۱+۱ و ۱+۱+۱+۱+۱.
def partitions(n):# ways[t] = the number of ways to write t as a sum of the parts allowed so far.ways = [1] + [0] * nrows = []for part in range(1, n + 1):for total in range(part, n + 1):ways[total] = ways[total] + ways[total - part]rows.append([part] + ways)return ways[n]
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
Call stack
- partitions()خط 1
توضیح
ایده
افراز عدد n یعنی نوشتنش به صورت جمع عددهای مثبت، بدون توجه به ترتیب: ۴ = ۳ + ۱ = ۲ + ۲ = ۲ + ۱ + ۱ = ۱ + ۱ + ۱ + ۱ (پنج افراز).
برنامه‌ریزی پویا
قسمت‌ها را یکی‌یکی مجاز می‌کنیم. وقتی قسمت part اضافه می‌شود، هر افراز total یا از part استفاده نمی‌کند (همان جواب قبلی)، یا دست‌کم یک part دارد (پس با حذفش افرازی از total − part می‌ماند):
ways[total] ← ways[total] + ways[total − part]
چون حلقه‌ی داخلی رو به بالا می‌رود، ways[total − part] همین حالا قسمت part را هم شامل می‌شود؛ پس یک قسمت می‌تواند چند بار بیاید. این همان الگوی مسئله‌ی خرد کردن پول است.
در trace به چه چیزی نگاه کنی
- هر سطر جدول کل آرایه‌ی
waysبعد از مجاز شدن یک قسمت است؛ ستون آخر جواب را در هر مرحله نشان می‌دهد.