Dynamic Programming আসলে কী¶

Smart recursion, যে solved প্রশ্নের উত্তর কখনো আবার দেয় না। এর চেয়ে রহস্যময় কিছু না।

1. যা জানো তা থেকে শুরু: recursion¶

Recursive function তো তুমি লেখোই (../06-recursion-and-backtracking/)। সবচেয়ে বিখ্যাতটা এই:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

সঠিক। Elegant। আর n ≥ 40 হলে ভয়াবহ রকম slow। কেন? Recursion slow বলে নয় — এই recursion-টা ভুলোমনা বলে।

2. Overlapping subproblems: fib(5)-এর call tree¶

fib(5) যত call করে, সব আঁকো:

                          fib(5)
                        /        \
                  fib(4)          fib(3)*
                 /      \         /     \
            fib(3)*   fib(2)*  fib(2)* fib(1)
            /    \     /   \    /   \
       fib(2)* fib(1) f(1) f(0) f(1) f(0)
        /   \
     fib(1) fib(0)

এবার repeat-গুলো গোনো (* দেওয়া জায়গায় একই value আবার computed হচ্ছে):

Call	Times computed
fib(5)	1
fib(4)	1
fib(3)	2
fib(2)	3
fib(1)	5
fib(0)	3

মাত্র 6-টা distinct প্রশ্নের (fib(0) থেকে fib(5)) উত্তর দিতে 15-টা call। অপচয়টা exponentially বাড়ে: fib(50) ~2^50-টা call করে 51-টা distinct প্রশ্নের উত্তর দিতে। Tree-টা বিশাল, কিন্তু তার প্রায় পুরোটাই déjà vu।

একটা problem-এর recursion যখন একই sub-প্রশ্ন বারবার করে, তখন বলি problem-টার overlapping subproblems আছে। এটাই DP requirement নম্বর এক।

3. Optimal substructure: অন্য requirement-টা¶

Optimal substructure মানে: বড় problem-এর best উত্তর তৈরি হয় subproblem-গুলোর best উত্তর থেকে।

B হয়ে A থেকে C-র shortest path = (shortest A→B) + (shortest B→C)। Optimal solution-এর টুকরোগুলো নিজেরাও optimal। ✔ DP চলে।
General graph-এ longest simple path এভাবে compose হয় না (sub-path-গুলো পুরো path জুড়ে "no repeated vertex" নিয়মের মাধ্যমে একে অপরকে আটকায়)। ✘ Obvious state-এ DP fail করে।

এটা formally প্রমাণ করতে হয় কালেভদ্রে। হাতে-কলমে test-টা: transition লেখার সময় জিজ্ঞেস করো — "subproblem-এর উত্তরগুলো কীভাবে এসেছে তা না জেনেই কি আমি সত্যিই আমার উত্তর বানাতে পারি?" হ্যাঁ হলে optimal substructure আছে।

দুটোই থাকলে DP চলে: overlapping subproblems + optimal substructure।

4. Fix #1 — Memoization (top-down): recursion + একটা খাতা¶

ঠিক সেই recursion-টাই রাখো। একটা খাতা (dictionary) যোগ করো। Solve করার আগে খাতা দেখো; solve করার পরে লিখে রাখো।

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:               # আগেই উত্তর দেওয়া? খাতা পড়ো
        return memo[n]
    if n <= 1:                  # base case অপরিবর্তিত
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]              # লিখে রাখো, তারপর return করো

Call tree-টার কী হয়? আগের প্রতিটা starred node ধসে যায় একটা খাতা-lookup-এ:

                          fib(5)
                        /        \
                  fib(4)         (memo: 2)
                 /      \
            fib(3)     (memo: 1)
            /    \
       fib(2)   (memo)
        /   \
   fib(1)  fib(0)

2^n call-এর tree হয়ে যায় n call-এর একটা chain plus সস্তা কিছু lookup। fib(5)-এর জন্য 15 calls → 9 calls; fib(50)-এর জন্য ~2^50 → 51।

একে বলে top-down DP, কারণ তুমি শুরু করো বড় প্রশ্ন থেকে (top), recurse করে নামো base case পর্যন্ত, আর পথে cache করতে করতে যাও।

5. Fix #2 — Tabulation (bottom-up): খাতাটা order-এ ভরো¶

Observation: খাতাটা যদি এমনিতেই ভরতে হয়, তাহলে order-এ ভরি না কেন — সবচেয়ে ছোট প্রশ্ন আগে, একটা সাধারণ loop দিয়ে? কোনো recursion-ই লাগবে না।

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)          # খাতাটা, array হিসেবে
    dp[0], dp[1] = 0, 1         # base case-গুলো আগে লেখা
    for i in range(2, n + 1):   # fill order: small -> large
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]                # উত্তরের ঠিকানা

এটা bottom-up DP: base case থেকে শুরু (bottom), আর উপরের দিকে বানাতে থাকো যতক্ষণ না আসল প্রশ্নটা fill হয়।

6. Memoization vs tabulation, পাশাপাশি, একই problem¶

Aspect	Memoization (top-down)	Tabulation (bottom-up)
Code-এর চেহারা	recursive function + dict	loop + array
Solve করার order	"যখন দরকার", recursion-চালিত	তুমি explicitly বাছো, small → large
কোন state-গুলো solved হয়	শুধু reachable-গুলো	সাধারণত সবগুলো
Risk	recursion depth limit (Python ~1000)	ভুল fill order garbage পড়ে
লেখার সহজতা	সবচেয়ে সহজ: recursion নাও, 4 লাইন যোগ করো	dependency order-টা জানতে হয়
Python-এ speed	slower (call overhead)	faster (tight loop)
Space optimization	কঠিন	সহজ (শুধু last row রাখো → `fib` O(1) space-এ)
আটকে গেলে best first move	YES — এখান থেকে শুরু করো	দরকার হলে পরে convert করো

এই repo-র হাতে-কলমে doctrine: think top-down, ship bottom-up। আগে recursion + memo design করো, কারণ সেটা তোমার ভাবনার আয়না; speed, space-সাশ্রয় বা Python-এর recursion limit এড়াতে হলে তখন table-এ convert করো।

Space নিয়ে আরেকটা কথা: fib_tab-এ dp[i] কেবল dp[i-1] আর dp[i-2] পড়ে। তাই পুরো array-টা সঙ্কুচিত হয়ে দুটো variable হয়ে যেতে পারে — O(1) space। "আমি শুধু আগের row/cell পড়ি" — এটা চোখে পড়াই standard DP space optimization।

7. যে vocabulary সব জায়গায় কাজে লাগবে¶

Term	Meaning
State	যে অল্প কয়টা সংখ্যা একটা subproblem-কে পুরো describe করে, যেমন "`dp[i]` = প্রথম i-টা item-এর উত্তর"
Transition	ছোট state থেকে একটা state বানানোর equation
Base case	যে state-গুলোর উত্তর কোনো transition ছাড়াই জানা
Fill order	যে order guarantee দেয় — প্রতিটা state computed হয় তার পড়া state-গুলোর পরে
Answer location	Table-এর কোন cell(-গুলো)-তে final উত্তর থাকে

এই পাঁচটাই ঠিক সেই 5-step doctrine, যা state-transition-thinking.md-তে শেখানো হয়েছে — এই folder-এর সবচেয়ে important file।

8. DP কখন apply হয়? একটা checklist¶

যেকোনো নতুন problem-এর বিরুদ্ধে এই প্রশ্নগুলো চালাও:

[ ] Problem-টা কি count of ways, একটা min/max value, না yes/no feasibility চাইছে? (DP-র তিনটে প্রিয় প্রশ্ন-ধরন।)
[ ] একটা subproblem-কে কি অল্প কয়েকটা integer দিয়ে describe করতে পারি (একটা index, একটা remaining budget, একটা position)?
[ ] কোনো brute-force recursion আদৌ exist করে? (Recurse করতে না পারলে DP-ও করতে পারবে না।)
[ ] ওই recursion কি একই sub-প্রশ্ন আবার করত? (Overlap।)
[ ] একটা state-এর উত্তর কি ছোট state-গুলো থেকে বানানো যায় তাদের ভেতরের history না জেনেই? (Optimal substructure।)
[ ] Distinct state-এর সংখ্যা কি যথেষ্ট ছোট — মোটামুটি ≤ 10^7 থেকে 10^8 simple operation?

উত্তরে যদি ঠিক কোন item-গুলো নেওয়া হয়েছিল লাগে, শুধু best value নয়, DP তবুও চলে: table-টা রাখো, তারপর fill শেষে table-এর ভেতর দিয়ে backtrack করো (প্রতিটা cell-এ জিজ্ঞেস করো "কোন choice আমাকে বানিয়েছে?")।

Red flag — DP apply হয় না (বা আরও চালাক state লাগে):

"State"-টাকে একটা unbounded history মনে রাখতে হতো (যেমন বড় n-এ visited city-গুলোর পুরো set — যদিও ছোট n হলে সেটাই bitmask DP, দেখো patterns.md)।
Subproblem-গুলো একদমই overlap করে না — তাহলে সাধারণ divide and conquer (merge sort-এর কায়দা) যথেষ্ট, খাতা লাগবে না।
একটা greedy exchange argument কাজ করে — তখন DP সঠিক, কিন্তু overkill।

9. একটা DP-র খরচ গোনা¶

Universal complexity formula:

time  = (number of distinct states) × (work per transition)
space = (number of states you must keep at once)

এই folder-এ যেগুলোর সাথে দেখা হবে:

Problem	States	Work per state	Time
fib / climbing stairs	n	O(1)	O(n)
coin change	amount	O(#coins)	O(amount × coins)
grid paths	m × n	O(1)	O(mn)
LIS (basic)	n	O(n)	O(n²)
0/1 knapsack	n × capacity	O(1)	O(n × capacity)
edit distance	len(a) × len(b)	O(1)	O(ab)

এরপর কোথায় যাবে¶

এই সবকিছুকে usable বানানোর skill-টা: state-transition-thinking.md।
Table-গুলো ভরতে দেখা: visual-explanation.md।
সবকিছুর runnable version: implementation.py।