برنامهنویسی پویا در یک بعد
آمادگی مصاحبهٔ الگوریتمی با Python
- In 90 minutes, recognize repeated subproblems in a choice tree; distinguish saving subproblem answers from enumerating every construction.
- Use the neutral problem of maximizing the sum of non-adjacent nonnegative array values, allowing the empty selection.
- Before the worked solution, independently specify what one indexed state means, its take-or-skip transition, and its base cases.
- Develop exponential recursion into Python memoization, then bottom-up evaluation and two-value rolling storage.
- Prove the transition by partitioning valid selections into taking or skipping the current value; justify evaluation order by induction.
- Count distinct states and work per state to derive O(n) time, O(n) memoized storage including the call stack, and O(1) auxiliary space for rolling evaluation.
- Test empty input, one element, two elements, equal values, and zeros; diagnose wrong base cases, premature overwriting, and caching a state that omits necessary information.
- Limit scope to one-dimensional states; reject this simple state when additional constraints require retaining more information.
اول زیرمسئله، بعد جدول
**مسئله دقیقاً چیست؟**
عددها نامنفی؛ انتخابها در جایگاههای غیرمجاور.
انتخاب خالی مجاز است؛ خروجی فقط مجموع بهینه است.
**بزرگترین عضو کافی نیست**
آرایه: \([4,5,4]\)
Greedy: انتخاب \(5\) ← ممنوعشدن هر دو \(4\)؛ مجموع \(5\).
انتخاب دو عضو غیرمجاور: \(4+4=8>5\).
**دو انتخاب برای هر عضو**
backtracking: برداشتن یا برنداشتن.
Brute Force درست است؛ اما فهرست همهٔ انتخابها را لازم نداریم.
**نقش Dynamic Programming**
چند مسیر تصمیم ← یک زیرمسئلهٔ یکسان ← استفادهٔ دوباره از جواب.
فقط بهترین مجموع را نگه میداریم.
**مکث: سه جمله بنویس**
state: بهترین جواب روی چند عضو اول دقیقاً چیست؟
دو انتخاب: با برداشتن یا برنداشتن عضو آخر، به کدام زیرمسئله میرسی؟
base case: جواب آرایهٔ خالی و تکعضوی چیست؟
هنوز نه جدول، نه حلقه.
دو انتخاب برای عضو آخر
\(\mathrm{best}(k)\): بیشترین مجموع معتبر از \(k\) عضو اول \(\mathrm{nums}\)، بدون برداشتن دو عضو مجاور؛ عضوها نامنفیاند.
**تعداد عضوها، نه index**
\[ 0\le k\le n,\qquad n=\operatorname{len}(\mathrm{nums}),\qquad \mathrm{answer}=\mathrm{best}(n) \]
index عضو آخر پیشوند: \(k-1\)
**پیشوند خالی**
\[ \mathrm{best}(0)=0 \]
**یک عضو**
\[ \mathrm{best}(1)=\mathrm{nums}[0] \]
نامنفیبودن عضو، برداشتنش را مجاز و بهینه میکند.
**عضو آخر را برنداریم**
\[ \mathrm{best}(k-1)\qquad(k\ge2) \]
**عضو آخر را برداریم**
\[ \mathrm{nums}[k-1]+\mathrm{best}(k-2) \]
عضو قبلی ممنوع است.
**بهترینِ دو شاخه**
\[ \mathrm{best}(k)=\max\!\left(\mathrm{best}(k-1),\;\mathrm{nums}[k-1]+\mathrm{best}(k-2)\right)\qquad(k\ge2) \]
هر انتخاب معتبر دقیقاً در یکی از دو شاخه است؛ هر شاخه نیز انتخاب معتبر میسازد.
**مثال: پیشوند خالی**
\[ \mathrm{nums}=[4,5,4],\qquad \mathrm{best}(0)=0 \]
**مثال: یک عضو**
\[ \mathrm{best}(1)=4 \]
**مثال: دو عضو**
\[ \mathrm{best}(2)=\max(4,\;5+0)=5 \]
**مثال: سه عضو و جواب نهایی**
\[ \mathrm{best}(3)=\max(5,\;4+4)=8 \]
در نسخهٔ recursive، دو base case و همین max را در best بنویس؛ خروجی maxnonadjacent، فراخوانی best با len آرایه است.
از فراخوانیهای تکراری تا memoization
```svg
<svg viewBox="0 0 800 550" xmlns="http://www.w3.org/2000/svg"><text x="220" y="35" text-anchor="middle" class="tm-text" font-size="20" direction="rtl">recursion خام</text><path d="M220 105 L125 160 M220 105 L315 160 M125 210 L65 265 M125 210 L185 265" class="tm-line" fill="none"/><rect x="160" y="60" width="120" height="45" rx="10" class="tm-surface"/><text x="220" y="89" text-anchor="middle" class="tm-text" font-size="18">\(\mathrm{best}(3)\)</text><rect x="65" y="160" width="120" height="50" rx="10" class="tm-surface"/><text x="125" y="191" text-anchor="middle" class="tm-text" font-size="18">\(\mathrm{best}(2)\)</text><rect x="255" y="160" width="120" height="50" rx="10" class="tm-gold"/><text x="315" y="191" text-anchor="middle" class="tm-text" font-size="18">\(\mathrm{best}(1)\)</text><rect x="5" y="265" width="120" height="50" rx="10" class="tm-gold"/><text x="65" y="296" text-anchor="middle" class="tm-text" font-size="18">\(\mathrm{best}(1)\)</text><rect x="140" y="265" width="120" height="50" rx="10" class="tm-surface"/><text x="200" y="296" text-anchor="middle" class="tm-text" font-size="18">\(\mathrm{best}(0)\)</text><text x="220" y="355" text-anchor="middle" class="tm-text-gold" font-size="18" direction="rtl">زیرمسئلهٔ یکسان، محاسبهٔ دوباره</text><text x="220" y="400" text-anchor="middle" class="tm-text" font-size="20">\(O(2^n)\)</text><rect x="430" y="60" width="350" height="255" rx="14" class="tm-soft"/><text x="605" y="93" text-anchor="middle" class="tm-text" font-size="21">memoization</text><text x="605" y="135" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">درخواست best برای یک پیشوند</text><text x="605" y="180" text-anchor="middle" class="tm-text-green" font-size="17" direction="rtl">موجود در memo؟ برگردان</text><text x="605" y="225" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">ناموجود؟ محاسبه با همان transition</text><text x="605" y="275" text-anchor="middle" class="tm-text-accent" font-size="17" direction="rtl">ذخیره در memo، سپس برگردان</text><rect x="435" y="330" width="340" height="90" rx="12" class="tm-green"/><text x="605" y="361" text-anchor="middle" class="tm-text" font-size="19">\(\mathrm{memo}[1]=4\)</text><text x="605" y="397" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">بار اول: ذخیره؛ بار بعد: خواندن</text><text x="400" y="458" text-anchor="middle" class="tm-text" font-size="18" direction="rtl">\(k=0,\ldots,n\) : \(n+1\) state؛ زمان \(O(n)\)</text><text x="400" y="493" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">memo و call stack: هرکدام \(O(n)\)؛ حافظهٔ کمکی \(O(n)\)</text><text x="400" y="530" text-anchor="middle" class="tm-text-accent" font-size="18" direction="rtl">memoization سرعت میدهد؛ درستی transition را تضمین نمیکند</text></svg>
```
از ترتیب وابستگی تا حافظهٔ ثابت
بیشینهٔ مجموع اعضای غیرمجاور؛ \(dp[k]\): جواب برای \(k\) عضو اول \(nums\).
**حالتهای پایه**
\[ \begin{gathered}n=\operatorname{len}(nums)\\ n=0\Rightarrow\operatorname{return}\ 0\\ dp=[0]\times(n+1),\qquad dp[1]=nums[0]\end{gathered} \]
پس از بررسی ورودی خالی، لیست را میسازیم.
**محاسبهٔ bottom-up**
\[ \begin{gathered}k=2,\ldots,n\\ dp[k]=\max\bigl(dp[k-1],\ nums[k-1]+dp[k-2]\bigr)\\ \operatorname{return}\ dp[n]\end{gathered} \]
در Python: حلقه با range(2, n + 1).
**توجیه با استقرا**
\[ \underbrace{dp[0],\ dp[1]}_{\text{base}}\quad\longrightarrow\quad\underbrace{dp[k-2],\ dp[k-1]}_{\text{ready and correct}}\quad\longrightarrow\quad dp[k] \]
پایهها درستاند؛ transition از جوابهای درست و آماده، جواب درست بعدی را میسازد.
**فقط دو جواب قبلی**
\[ \begin{gathered}\texttt{maxnonadjacent(nums)}\\ prev2=0,\qquad prev1=0\end{gathered} \]
پیش از پردازش هر عضو، دو متغیر جوابهای دو مرحلهٔ قبلی را نگه میدارند.
**حلقهٔ rolling؛ ترتیب مهم است**
\[ \begin{aligned}&\text{for }x\text{ in }nums:\\&\quad current=\max(prev1,\ prev2+x)\\&\quad prev2=prev1\\&\quad prev1=current\\&\operatorname{return}\ prev1\end{aligned} \]
ابتدا current را حساب کن؛ سپس prev2 مقدار قبلی prev1 را میگیرد. ورودی خالی نیز بدون اجرای حلقه، صفر میدهد.
**عضو اول: 4**
\[ \begin{aligned}nums&=[4,5,4]\\current&=\max(0,0+4)=4\(prev2,prev1)&=(0,4)\end{aligned} \]
**عضو دوم: 5**
\[ \begin{aligned}current&=\max(4,0+5)=5\(prev2,prev1)&=(4,5)\end{aligned} \]
**عضو آخر: 4**
\[ \begin{aligned}current&=\max(5,4+4)=\max(5,8)=8\(prev2,prev1)&=(5,8)\\\operatorname{return}\ prev1&=8\end{aligned} \]
**زمان خطی، حافظهٔ ثابت**
\[ T(n)=O(n),\qquad S_{\mathrm{aux}}(n)=O(1) \]
هر عضو یک بار پردازش میشود؛ فقط چند متغیر نگه میداریم.
دفاع از راهحل با تست
تستهای مرزی، ترتیب بهروزرسانی و کافیبودن state
**ورودی خالی**
\[ [\,]\;:\quad \mathrm{prev1}=0\;\Longrightarrow\;0 \]
حلقه اجرا نمیشود.
**یک عضو**
\[ [6]\;:\quad \mathrm{current}=\max(0,0+6)=6 \]
**دو عضو؛ نه دو همسایه با هم**
\[ \begin{aligned}[2,7]:\quad (\mathrm{prev2},\mathrm{prev1})&=(0,0)\\x=2:\quad \mathrm{current}&=\max(0,0+2)=2\quad\Rightarrow(0,2)\\x=7:\quad \mathrm{current}&=\max(2,0+7)=7\quad\Rightarrow(2,7)\end{aligned} \]
**مقدارهای برابر؛ جایگاههای جدا**
\[ \begin{aligned}[4,4,4]:\quad \max(0,0+4)&=4\\\max(4,0+4)&=4\\\max(4,4+4)&=8\end{aligned} \]
عضو اول و سوم قابل انتخاباند.
**همه صفر**
\[ \begin{aligned}[0,0,0]:\quad \max(0,0+0)&=0\\\max(0,0+0)&=0\\\max(0,0+0)&=0\end{aligned} \]
ورودی خالی را هم بررسی کن؛ از خانهٔ ناموجود نخوان.
**خطای rolling**
\[ \begin{aligned}\mathrm{prev1}&\leftarrow\mathrm{current}\\\mathrm{prev2}&\leftarrow\mathrm{prev1}\[2,7]:\quad (0,0)&\xrightarrow{x=2}(2,2)\\\mathrm{current}&=\max(2,2+7)=9\end{aligned} \]
نامعتبر: دو عضو همسایه با هم جمع شدهاند.
**ترتیب امن بهروزرسانی**
\[ \begin{aligned}\mathrm{current}&\leftarrow\max(\mathrm{prev1},\mathrm{prev2}+x)\\\mathrm{prev2}&\leftarrow\mathrm{prev1}\\\mathrm{prev1}&\leftarrow\mathrm{current}\end{aligned} \]
ابتدا current با مقدارهای قدیمی؛ سپس prev2 و بعد prev1.
**کلید cache باید کافی باشد**
\[ \mathrm{state}=(\mathrm{index},\mathrm{previousSelected}) \]
در recursion با وضعیت انتخاب عضو قبلی، index بهتنهایی کافی نیست: مجازبودن انتخاب فرق میکند. تعریف بهترین مجموع پیشوند، با رفتن به دو عضو کمتر این وابستگی را حذف میکند.
**شرط تازه؛ بازبینی state**
\[ \mathrm{count}=2 \]
انتخاب دقیقاً دو عضو: بهترین مجموع پیشوند بهتنهایی کافی نیست؛ اطلاعات تعداد انتخابها هم لازم است.
بازگشت به دوره