Visual Explanation — DP Table-গুলো ভরতে দেখা

Table একটা একটা cell করে ভরতে দেখার মুহূর্ত থেকেই DP আর abstract থাকে না। এই file দুটো classic table frame by frame ভরেছে, আর একটা recursion tree দেখিয়েছে memoization-এর আগে ও পরে।

---

1. Grid paths, 3 × 3, frame by frame

Task: top-left থেকে bottom-right-এ path গোনো, শুধু right বা down চলে। State: dp[r][c] = cell (r, c)-তে পৌঁছানো path। Transition: dp[r][c] = top + left।

frame 0 — empty grid, base case planted
    +---+---+---+
    | 1 | . | . |        dp[0][0] = 1: one way to stand at the start
    +---+---+---+
    | . | . | . |
    +---+---+---+
    | . | . | . |
    +---+---+---+

frame 1 — finish row 0 (only "from the left" exists)
    +---+---+---+
    | 1 | 1 | 1 |        each cell = left neighbor (no row above)
    +---+---+---+
    | . | . | . |
    +---+---+---+
    | . | . | . |
    +---+---+---+

frame 2 — row 1, left to right
    dp[1][0] = top = 1
    dp[1][1] = top + left = 1 + 1 = 2
    dp[1][2] = top + left = 1 + 2 = 3
    +---+---+---+
    | 1 | 1 | 1 |
    +---+---+---+
    | 1 | 2 | 3 |
    +---+---+---+
    | . | . | . |
    +---+---+---+

frame 3 — row 2, left to right
    dp[2][0] = top = 1
    dp[2][1] = top + left = 2 + 1 = 3
    dp[2][2] = top + left = 3 + 3 = 6
    +---+---+---+
    | 1 | 1 | 1 |
    +---+---+---+
    | 1 | 2 | 3 |
    +---+---+---+
    | 1 | 3 | 6 |   -> answer: 6 paths
    +---+---+---+

শেষ cell-টার transition arrow, এঁকে দেখালে:

            | 3 |
              v
    | 3 | -> [6]      every cell literally equals "value above + value to the left"

Sanity check: একটা 3×3 grid-এ লাগে ঠিক 2-টা right আর 2-টা down, কোনো একটা order-এ — "4-টা move-এর মধ্যে 2-টা বাছো" = 6। Table-ও তাই বলছে। (কাত হয়ে শুয়ে থাকা Pascal's triangle-টা হয়তো চিনতে পারছ।)

2. Coin change, amount 11, coins [1, 2, 5], frame by frame

Task: 11 বানাতে সবচেয়ে কম coin। State: dp[a] = amount a-র জন্য min coin। Transition: যে coin-গুলো আঁটে, তাদের উপর dp[a] = 1 + min(dp[a-1], dp[a-2], dp[a-5])। ∞ = এখনো বানানো যায় বলে জানা নেই।

frame 0 — base case
    a:    0   1   2   3   4   5   6   7   8   9  10  11
    dp:   0   ∞   ∞   ∞   ∞   ∞   ∞   ∞   ∞   ∞   ∞   ∞

frame 1 — a = 1:  1 + min(dp[0]) = 1                      (coin 1)
frame 2 — a = 2:  1 + min(dp[1], dp[0]) = 1               (coin 2 wins)
frame 3 — a = 3:  1 + min(dp[2], dp[1]) = 2               (2+1)
frame 4 — a = 4:  1 + min(dp[3], dp[2]) = 2               (2+2)
frame 5 — a = 5:  1 + min(dp[4], dp[3], dp[0]) = 1        (coin 5 wins!)
    a:    0   1   2   3   4   5   6   7   8   9  10  11
    dp:   0   1   1   2   2   1   .   .   .   .   .   .

frame 6 — a = 6:  1 + min(dp[5], dp[4], dp[1]) = 1+1 = 2  (5+1)
frame 7 — a = 7:  1 + min(dp[6], dp[5], dp[2]) = 1+1 = 2  (5+2)
frame 8 — a = 8:  1 + min(dp[7], dp[6], dp[3]) = 1+2 = 3  (5+2+1)
frame 9 — a = 9:  1 + min(dp[8], dp[7], dp[4]) = 1+2 = 3  (5+2+2)
frame 10 — a = 10: 1 + min(dp[9], dp[8], dp[5]) = 1+1 = 2 (5+5)
frame 11 — a = 11: 1 + min(dp[10], dp[9], dp[6]) = 1+2 = 3 (5+5+1)

    a:    0   1   2   3   4   5   6   7   8   9  10  11
    dp:   0   1   1   2   2   1   2   2   3   3   2   3
                                                      ^
                                            answer: 3 coins (5+5+1)

a = 11-এর transition-টা, number line-এ পেছনদিকের লাফ হিসেবে আঁকা:

       coin 5            coin 2   coin 1
   6 <-----------\   9 <----\  10 <-\
   .   .   .   .  \   .      \  .    \
   0 1 2 3 4 5 [6] 7 8 [9] [10] (11)
                2        3    2
   dp[11] = 1 + min(2, 3, 2) = 3

আসল coin-গুলো উল্টো পড়ে বের করা (table-টা backtrack করা): 11-তে winner ছিল coin 5 (বা 10 হয়ে coin 1 — tie চলে) → 6-এ যাও; 6-এ winner ছিল coin 5 → 1-এ যাও; 1-এ winner ছিল coin 1 → 0-তে যাও। জমা coin: 5, 5, 1। Table জমায় value; winning choice-গুলোর path জমায় solution-টা নিজেই।

3. Recursion tree: memoization-এর আগে আর পরে

সাধারণ recursion-এ fib(5) — 15-টা node, repeat-গুলো * দিয়ে marked:

                          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)

Memoization-সহ fib(5) — প্রতিটা value-র প্রথম visit সেটাকে compute করে; পরের প্রতিটা visit একটা খাতা-lookup (▣):

                          fib(5)
                        /        \
                  fib(4)          ▣ fib(3)   <- looked up, no subtree grows
                 /      \
            fib(3)       ▣ fib(2)
            /    \
       fib(2)    ▣ fib(1)
        /   \
     fib(1) fib(0)

n = 5-এ 15 node → 9 node। Leaf-এর উপরের প্রতিটা node-এর ডান child আর tree রইল না, হয়ে গেল একটা মাত্র lookup। n = 50 হলে পার্থক্যটা ~2^50 node বনাম 99: গোটা exponential ঝোপটা ছেঁটে নেমে আসে একটা শিরদাঁড়া plus কিছু lookup-এ।

growth picture:

naive:        memo:
   n=5:  15      9
   n=10: 177    19
   n=20: 21891  39
   n=50: ~2^50  99        the notebook flattens the explosion

4. সাধারণ mental movie-টা

এই folder-এর প্রতিটা DP একই ফিল্ম চালায়:

1. draw the empty table          (the states)
2. plant the base cases          (known answers)
3. sweep in fill order           (arrows always point at finished cells)
4. each cell = combine(earlier cells)   (the transition)
5. read the answer cell          (and optionally backtrack the choices)

নতুন problem-এ আটকে গেলে code debug কোরো না — একটা ছোট্ট table হাতে ভরো (n = 4 বা 5)। দশবারের নয়বার bug-টা frame 3-এর মধ্যেই চোখে পড়ে: ভুল base case, ভুল arrow, নাহয় ভুল fill order। DP-র জন্য এ যাবত বানানো সেরা debugger হলো পেন্সিল।