Dynamic programming-এর ভিত্তি — memoization আর tabulation

১ · একই হিসাব বারবার — Fibonacci-র বিস্ফোরণ

পর্ব ০৭-এ Fibonacci সংখ্যার রিকার্সিভ সংজ্ঞা দেখেছেন: fib(0) = 0, fib(1) = 1, আর fib(n) = fib(n − 1) + fib(n − 2). কোডে এটি তিন লাইনের, আর দেখতে নির্ভুল। কিন্তু fib(5) ডাকলে কী কী কল হয়, তার পুরো recursion tree লিখে দেখুন:

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ fib(1)
│  └─ fib(2)          <- again
│     ├─ fib(1)
│     └─ fib(0)
└─ fib(3)             <- again: the whole branch
   ├─ fib(2)          <- again
   │  ├─ fib(1)
   │  └─ fib(0)
   └─ fib(1)

১৫টি কল, কিন্তু আলাদা প্রশ্ন মাত্র ৬টি — fib(0) থেকে fib(5). fib(3) দুবার, fib(2) তিনবার, fib(1) পাঁচবার হিসাব হয়েছে। n বাড়লে অবস্থা ভয়াবহ হয়।

কল গোনার প্রমাণ. C(n) = fib(n)-এর মোট কল। C(0) = C(1) = 1, আর n ≥ 2 হলে C(n) = 1 + C(n − 1) + C(n − 2). দাবি: C(n) = 2F(n+1) − 1, যেখানে F হলো Fibonacci সংখ্যা। Induction: C(0) = 2·1 − 1 = 1, C(1) = 2·1 − 1 = 1. ধরে নিন n − 1 আর n − 2-এর জন্য সত্য; তাহলে C(n) = 1 + (2F(n) − 1) + (2F(n−1) − 1) = 2(F(n) + F(n−1)) − 1 = 2F(n+1) − 1. ∎ যেহেতু F(n) ≈ φⁿ/√5, যেখানে φ ≈ 1.618 হলো golden ratio, সময় Θ(φⁿ) — সূচকীয়। জায়গা অবশ্য শুধু call stack-এর গভীরতা, Θ(n).

n = 50-এ চার হাজার কোটির বেশি কল — দ্রুত C++-এও সেটি অনেক সেকেন্ডের কাজ, আর Python-এ ঘণ্টার হিসাবে। অথচ ডানের কলামে মাত্র ৯৯টি কল। পার্থক্য একটাই: একবার হিসাব করা উত্তর মনে রাখা।

২ · DP-র দুই শর্ত — overlapping subproblems আর optimal substructure

Dynamic programming (সংক্ষেপে DP) একটি নকশার কৌশল: বড় সমস্যাকে ছোট উপসমস্যায় ভাঙা, প্রতিটি উপসমস্যার উত্তর একবারই হিসাব করে রাখা, আর বড় উত্তর সেগুলো জুড়ে বানানো। কৌশলটি কাজ করে দুটি শর্ত পূরণ হলে।

শর্ত ১ — overlapping subproblems: রিকার্শন চলার সময় একই উপসমস্যা বারবার আসে, আর মোট আলাদা উপসমস্যার সংখ্যা ছোট (সাধারণত polynomial). fib-এ আলাদা প্রশ্ন n + 1 টি, অথচ কল সূচকীয়। তুলনা করুন merge sort-এর সাথে (পর্ব ২১): সেখানে প্রতিটি অর্ধেক আলাদা টুকরো, কোনো টুকরো দুবার সাজানো হয় না। তাই merge sort-এ খাতা রেখে কোনো লাভ নেই — ওটি খাঁটি divide and conquer.

শর্ত ২ — optimal substructure: পুরো সমস্যার সেরা উত্তরের ভেতরের অংশগুলোও নিজ নিজ উপসমস্যার সেরা উত্তর। উদাহরণ: মিরপুর থেকে মতিঝিলের সবচেয়ে ছোট পথ যদি ফার্মগেট হয়ে যায়, তাহলে সেই পথের “মিরপুর → ফার্মগেট” অংশটিও মিরপুর থেকে ফার্মগেটের সবচেয়ে ছোট পথ।

প্রমাণ — cut-and-paste যুক্তি. ধরুন P একটি সংক্ষিপ্ততম পথ s ⇝ t, যা v দিয়ে যায়: P = P₁ (s ⇝ v) + P₂ (v ⇝ t). যদি P₁ s থেকে v-এর সংক্ষিপ্ততম না হতো, তাহলে আরও ছোট একটি Q থাকত। P₁ কেটে Q বসালে (cut and paste) Q + P₂ হতো P-এর চেয়ে ছোট একটি s ⇝ t walk — কিন্তু P সবচেয়ে ছোট, বিরোধ। (ঋণাত্মক cycle না থাকলে walk থেকে লুপ কেটে simple path পাওয়া যায়, খরচ বাড়ে না।) ∎ ঠিক এই যুক্তিই Bellman-Ford আর Floyd-Warshall-এর (পর্ব ৪৪) ভিত্তি ছিল।

Richard Bellman ১৯৫৭ সালে দ্বিতীয় শর্তটিকে (optimal substructure) বলেছিলেন principle of optimality: একটি সেরা নীতির বৈশিষ্ট্য হলো, শুরুর অবস্থা আর প্রথম সিদ্ধান্ত যা-ই হোক, বাকি সিদ্ধান্তগুলো প্রথম সিদ্ধান্তের ফলে তৈরি অবস্থার জন্য নিজেরাই একটি সেরা নীতি।

৩ · Memoization — ওপর থেকে নিচে, রিকার্শন আর খাতা

সবচেয়ে সহজ উপায়: সরল রিকার্সিভ ফাংশনটি অপরিবর্তিত রাখুন, শুধু একটি খাতা যোগ করুন। হিসাব শুরুর আগে দেখুন উত্তর খাতায় আছে কি না; থাকলে সেটিই ফেরত দিন, না থাকলে হিসাব করে লিখে রাখুন। এর নাম memoization — শব্দটি ১৯৬৮ সালে Donald Michie-র দেওয়া, “memo” (স্মারকলিপি) থেকে। এটি top-down DP: বড় প্রশ্ন থেকে শুরু, প্রয়োজনমতো ছোট প্রশ্নে নামা।

Pseudocode — memoized Fibonacci (0-based)

memo = empty table                      // "not computed yet" for every n
fib(n):
    if n < 2:  return n                 // base cases
    if memo[n] is filled:  return memo[n]   // seen before: just read the notebook
    memo[n] = fib(n - 1) + fib(n - 2)   // first time: compute once, write down
    return memo[n]

জটিলতা: প্রতিটি n ≥ 2 একবারই পুরো হিসাব হয় (প্রথমবার), আর তখন ঠিক দুটি কল করে; পরের যেকোনো ডাক O(1)-এ খাতা থেকে ফেরে। মোট কল 2n − 1, প্রতিটি O(1) কাজ — Θ(n) সময়. খাতা Θ(n), call stack-এর গভীরতাও Θ(n) — মোট Θ(n) জায়গা. খাতা হিসেবে array (n ছোট আর পূর্ণসংখ্যা হলে) বা hash table (অবস্থা জটিল হলে, পর্ব ৩২) — দুটোই চলে।

৪ · Tabulation — নিচ থেকে ওপরে, আর rolling array

উল্টো দিক থেকেও ভাবা যায়: বড় প্রশ্নের অপেক্ষা না করে সবচেয়ে ছোট উপসমস্যা থেকে শুরু করে একটি টেবিল ক্রমানুসারে ভরে ফেলুন, যাতে প্রতিটি ঘর ভরার সময় তার দরকারি ঘরগুলো আগেই ভরা থাকে। এর নাম tabulation, বা bottom-up DP. কোনো রিকার্শন নেই — শুধু একটি লুপ।

একটি পরিচিত সমস্যায় দেখুন। সিঁড়ি ওঠা (climbing stairs): ফুটওভার ব্রিজের সিঁড়িতে n টি ধাপ। আপনি একবারে ১ ধাপ বা ২ ধাপ উঠতে পারেন। মোট কতভাবে ওপরে পৌঁছানো যায়? শেষ চালটি ভাবুন: n-এ পৌঁছানোর ঠিক আগে আপনি ছিলেন n − 1-এ (তারপর ১ ধাপ) অথবা n − 2-এ (তারপর ২ ধাপ) — দুই দল আলাদা, কেউ দুই দলে পড়ে না। তাই ways[n] = ways[n − 1] + ways[n − 2], base case ways[0] = 1 (কিছু না করাও একটি উপায়) আর ways[1] = 1. এটি আসলে Fibonacci: ways[n] = F(n + 1).

শেষ ধাপের কৌশলটির নাম rolling array: যখন recurrence শুধু শেষ k টি সারি বা ঘরের ওপর নির্ভর করে, তখন শুধু সেগুলোই রাখুন। গ্রিডের DP-তে (অংশ ৬) পুরো R × C টেবিলের বদলে একটি সারি, অর্থাৎ Θ(C) জায়গা। তবে একটি দাম আছে: পুরোনো ঘর মুছে গেলে কোন পথে উত্তর এসেছিল তা আর বের করা যায় না — শুধু সংখ্যাটি থাকে। সেজন্য অংশ ৬-এ আলাদা একটি পছন্দের টেবিল রাখব।

নিচের প্রোগ্রাম তিনটি পদ্ধতি পাশাপাশি চালায়, আর সরল ও memo পদ্ধতির কল গোনে:

#include <cstdio>
#include <initializer_list>
#include <vector>
using namespace std;
long long calls = 0;
long long fib_naive(int n) {                         // plain recursion: no memory at all
    ++calls;
    return n < 2 ? n : fib_naive(n - 1) + fib_naive(n - 2);
}
long long fib_memo(int n, vector<long long>& memo) {   // top-down: same recursion + a notebook
    ++calls;
    if (n < 2) return n;
    if (memo[n] == -1) memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}
long long fib_table(int n) {                         // bottom-up: fill dp[0..n] left to right
    vector<long long> dp(n + 1, 0);
    if (n >= 1) dp[1] = 1;
    for (int i = 2; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}
long long fib_rolling(int n) {                       // only the last two values are ever needed
    long long a = 0, b = 1;
    for (int i = 0; i < n; ++i) { long long c = a + b; a = b; b = c; }
    return a;
}
int main() {
    for (int n : {10, 20, 25}) {
        calls = 0;
        long long x = fib_naive(n), naive_calls = calls;
        vector<long long> memo(n + 1, -1);
        calls = 0;
        long long y = fib_memo(n, memo);
        printf("n=%2d naive=%lld calls=%lld | memo=%lld calls=%lld | table=%lld | rolling=%lld\n",
               n, x, naive_calls, y, calls, fib_table(n), fib_rolling(n));
    }
    printf("fib(90) = %lld = %lld\n", fib_table(90), fib_rolling(90));
}

n=10 naive=55 calls=177 | memo=55 calls=19 | table=55 | rolling=55
n=20 naive=6765 calls=21891 | memo=6765 calls=39 | table=6765 | rolling=6765
n=25 naive=75025 calls=242785 | memo=75025 calls=49 | table=75025 | rolling=75025
fib(90) = 2880067194370816120 = 2880067194370816120

calls = 0

def fib_naive(n):                      # plain recursion: no memory at all
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

def fib_memo(n, memo):                 # top-down: same recursion + a notebook
    global calls
    calls += 1
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

def fib_table(n):                      # bottom-up: fill dp[0..n] left to right
    dp = [0] * (n + 1)
    if n >= 1:
        dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def fib_rolling(n):                    # only the last two values are ever needed
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

for n in (10, 20, 25):
    calls = 0
    x = fib_naive(n)
    naive_calls = calls
    calls = 0
    y = fib_memo(n, {})
    print(f"n={n:2} naive={x} calls={naive_calls} | memo={y} calls={calls}"
          f" | table={fib_table(n)} | rolling={fib_rolling(n)}")
print("fib(90) =", fib_table(90), "=", fib_rolling(90))

n=10 naive=55 calls=177 | memo=55 calls=19 | table=55 | rolling=55
n=20 naive=6765 calls=21891 | memo=6765 calls=39 | table=6765 | rolling=6765
n=25 naive=75025 calls=242785 | memo=75025 calls=49 | table=75025 | rolling=75025
fib(90) = 2880067194370816120 = 2880067194370816120

৫ · DP-র রেসিপি — ছয়টি ধাপ, আর জটিলতার এক সূত্র

নতুন DP সমস্যায় সবচেয়ে কঠিন কাজ কোড লেখা নয় — সঠিক উপসমস্যা খুঁজে পাওয়া। প্রায় সব DP এই ছয়টি ধাপে লেখা যায়:

1. অবস্থা কথায় লিখুন. “dp[i] = …” একটি পূর্ণ বাক্যে, যেমন “প্রথম i দিনে সর্বোচ্চ কত আয় সম্ভব”. বাক্যটি স্পষ্ট না হলে recurrence-ও ভুল হবে। এই সংজ্ঞাই DP-র অবস্থা.
2. Recurrence. শেষ সিদ্ধান্তটি নিয়ে ভাবুন (“শেষ দিনে কাজ করব কি না”, “শেষ চাল ১ ধাপ না ২ ধাপ”), আর প্রতিটি সম্ভাব্য পছন্দকে ছোট অবস্থায় নামান। এক অবস্থা থেকে অন্যটিতে যাওয়াই transition.
3. Base case. যে অবস্থাগুলো recurrence ছাড়াই জানা — খালি ইনপুট, প্রথম ঘর।
4. হিসাবের ক্রম. প্রতিটি অবস্থার আগে তার নির্ভর অবস্থাগুলো — সাধারণত i বাড়িয়ে, বা সারি ধরে। Memoization-এ রিকার্শন নিজেই ক্রম ঠিক করে।
5. উত্তর কোথায়. dp[n]? dp-র সর্বোচ্চ মান? শেষ সারির কোনো ঘর? অনেক ভুল শুধু এখানেই।
6. সমাধান পুনর্গঠন. শুধু সংখ্যা নয়, আসল পছন্দগুলো চাইলে — কোন দিনগুলো, কোন পথ — প্রতিটি অবস্থায় কোন পছন্দ জিতেছিল তা রাখুন, আর উত্তর থেকে পেছনে হাঁটুন।

fib-এ অবস্থা n + 1 টি, প্রতিটিতে ২টি পুরোনো মান পড়া — Θ(n). R × C গ্রিডে অবস্থা RC টি, প্রতিটিতে ২টি পছন্দ — Θ(RC). পর্ব ৫৩-এর knapsack-এ অবস্থা n × W, প্রতিটিতে ২টি পছন্দ — Θ(nW). আর জায়গা = যত অবস্থা একসাথে মনে রাখতে হয় (rolling করলে কম)। কোনো DP-র সময় বলতে বললে আগে এই দুটি সংখ্যা আলাদা করে লিখুন।

রেসিপিতে একটি সমস্যা — ওভারটাইমের সেরা দিন (house robber)

একটি গার্মেন্টস কারখানায় ঈদের আগে ৫ দিন ওভারটাইমের সুযোগ, প্রতিদিনের মজুরি a = [5, 3, 4, 11, 2] (শত টাকায়)। নিয়ম: পরপর দুই দিন ওভারটাইম করা যাবে না। সর্বোচ্চ কত আয়? ইন্টারভিউতে এটিই “house robber” নামে পরিচিত — পাশাপাশি দুটি বাড়ি একসাথে নেওয়া যায় না।

অবস্থা: best[i] = প্রথম i দিনের মধ্যে, নিয়ম মেনে, সর্বোচ্চ আয়। Recurrence: i-তম দিনে কাজ না করলে best[i − 1]; করলে (i − 1)-তম দিন বাদ, তাই best[i − 2] + a[i]. সুতরাং best[i] = max(best[i − 1], best[i − 2] + a[i]). Base: best[0] = 0, best[1] = a[1]. ক্রম: i = 2, 3, …, n. উত্তর: best[n]. Optimal substructure কেন: একটি সেরা পরিকল্পনা যদি শেষ দিন বাদ দেয়, তার বাকিটা প্রথম n − 1 দিনের একটি বৈধ পরিকল্পনা — সেটি সেরা না হলে বদলে দিয়ে মোট বাড়ানো যেত (cut-and-paste); শেষ দিন নিলে একই যুক্তি প্রথম n − 2 দিনে।

Kadane-কে DP-র চোখে

পর্ব ১০-এ maximum subarray-এর Kadane সমাধান দেখেছিলেন। এবার রেসিপিতে লিখুন। অবস্থা: end[i] = ঠিক i-তে শেষ হওয়া subarray-গুলোর মধ্যে সর্বোচ্চ যোগফল। “i পর্যন্ত সেরা” নয় — শেষ হওয়ার শর্তটিই recurrence-কে সহজ করে। Recurrence: i-তে শেষ হওয়া সেরা অংশটি হয় শুধু a[i], নয়তো i − 1-এ শেষ হওয়া সেরা অংশের সাথে a[i]: end[i] = max(a[i], end[i − 1] + a[i]). Base: end[0] = a[0]. উত্তর: শেষ ঘরে নয় — সব end[i]-এর সর্বোচ্চ। a = [−2, 1, −3, 4, −1, 2, 1, −5, 4]-এ:

i      :  0   1   2   3   4   5   6   7   8
a[i]   : -2   1  -3   4  -1   2   1  -5   4
end[i] : -2   1  -2   4   3   5   6   1   5      answer = max = 6  (i = 3..6)

অবস্থা n টি, transition O(1): Θ(n) সময়, আর end[i − 1] ছাড়া কিছু লাগে না বলে Θ(1) জায়গা — Kadane আসলে rolling array-সহ একটি DP. এখান থেকে একটি সাধারণ শিক্ষা: “উত্তর কোথায়” ধাপটি সবসময় dp[n] নয়।

৬ · ঢাকার রাস্তার গ্রিড — পথ গোনা আর সবচেয়ে কম জ্যামের পথ

ধরুন শহরের একটি অংশ ৪ সারি × ৫ কলামের মোড়ের গ্রিড। শুরু ওপরের বাঁ কোণ (0,0), ধরুন মিরপুরের দিকের একটি মোড়; গন্তব্য নিচের ডান কোণ (3,4), মতিঝিলের দিকে। প্রতিটি চালে আপনি শুধু ডানে (পূর্বে, R) বা নিচে (দক্ষিণে, D) যান — পেছনে যাওয়ার কারণ নেই। কিছু মোড় বন্ধ (#): রাস্তা খোঁড়া বা জলাবদ্ধ। প্রতিটি খোলা মোড়ের সংখ্যা সেখানে জ্যামে আটকে থাকার মিনিট।

        0  1  2  3  4
   0 │  3  2  4  1  2      start = (0,0)
   1 │  1  #  1  3  1
   2 │  2  1  2  #  2
   3 │  #  3  1  2  1      goal  = (3,4)

প্রশ্ন ১ — কয়টি পথ? অবস্থা: ways[i][j] = (0,0) থেকে (i,j)-তে পৌঁছানোর পথের সংখ্যা। শেষ চালটি এসেছে ওপর থেকে বা বাঁ থেকে — দুই দল আলাদা: ways[i][j] = ways[i − 1][j] + ways[i][j − 1]; বন্ধ মোড়ে ০; base ways[0][0] = 1; গ্রিডের বাইরের ঘর ০ ধরা হয়। সারি ধরে, বাঁ থেকে ডানে ভরলে প্রতিটি ঘরের ওপরের আর বাঁয়ের ঘর আগেই ভরা।

প্রশ্ন ২ — সবচেয়ে কম জ্যামের পথ (minimum cost path). অবস্থা: cost[i][j] = (0,0) থেকে (i,j) পর্যন্ত কোনো পথে মোট জ্যামের সর্বনিম্ন মিনিট (দুই প্রান্তের মোড়সহ)। Recurrence: cost[i][j] = w[i][j] + min(cost[i − 1][j], cost[i][j − 1]); বন্ধ মোড় বা গ্রিডের বাইরে ∞. পুনর্গঠনের জন্য একটি পছন্দের টেবিল came[i][j]: D (ওপর থেকে এসেছি) বা R (বাঁ থেকে)। সমান হলে D নেওয়া হবে — এই নিয়ম আগে ঠিক না করলে দুটি সঠিক প্রোগ্রাম দুটি আলাদা (সমান খরচের) পথ ছাপতে পারে।

দুটি প্রশ্ন একই লুপে, একই প্রোগ্রামে:

#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
int main() {
    vector<string> grid = {"32412",              // digit = minutes of jam at that crossing
                           "1#131",              // '#' = road closed (dug up / flooded)
                           "212#2",
                           "#3121"};
    const int R = grid.size(), C = grid[0].size(), INF = 1e9;
    vector<vector<long long>> ways(R, vector<long long>(C, 0));
    vector<vector<int>> cost(R, vector<int>(C, INF));
    vector<string> came(R, string(C, '.'));      // choice table: 'D' = from above, 'R' = from the left
    for (int i = 0; i < R; ++i)                  // row by row = a topological order of the cells
        for (int j = 0; j < C; ++j) {
            if (grid[i][j] == '#') continue;     // closed crossing: 0 ways, infinite cost
            int w = grid[i][j] - '0';
            if (i == 0 && j == 0) { ways[0][0] = 1; cost[0][0] = w; continue; }
            int up = i > 0 ? cost[i - 1][j] : INF, left = j > 0 ? cost[i][j - 1] : INF;
            ways[i][j] = (i > 0 ? ways[i - 1][j] : 0) + (j > 0 ? ways[i][j - 1] : 0);
            if (min(up, left) < INF) { cost[i][j] = w + min(up, left); came[i][j] = up <= left ? 'D' : 'R'; }
        }
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) printf("%s%2lld", j ? " " : "", ways[i][j]);
        for (int j = 0; j < C; ++j) { const char* sep = j ? " " : "     ";
            if (cost[i][j] < INF) printf("%s%2d", sep, cost[i][j]); else printf("%s #", sep); }
        for (int j = 0; j < C; ++j) printf("%s%c", j ? " " : "     ", came[i][j]);
        printf("\n");
    }
    printf("paths: %lld  min cost: %d\n", ways[R - 1][C - 1], cost[R - 1][C - 1]);
    int i = R - 1, j = C - 1;
    string moves, path = "(" + to_string(i) + "," + to_string(j) + ")";
    while (i || j) {                             // walk the choice table backwards
        moves = came[i][j] + moves;
        if (came[i][j] == 'D') --i; else --j;
        path = "(" + to_string(i) + "," + to_string(j) + ") " + path;
    }
    printf("moves: %s  path: %s\n", moves.c_str(), path.c_str());
}

 1  1  1  1  1      3  5  9 10 12     . R R R R
 1  0  1  2  3      4  # 10 13 13     D . D D D
 1  1  2  0  3      6  7  9  # 15     D R R . D
 0  1  3  3  6      # 10 10 12 13     . D D R R
paths: 6  min cost: 13
moves: DDRRDRR  path: (0,0) (1,0) (2,0) (2,1) (2,2) (3,2) (3,3) (3,4)

grid = ["32412",                       # digit = minutes of jam at that crossing
        "1#131",                       # '#' = road closed (dug up / flooded)
        "212#2",
        "#3121"]
R, C, INF = len(grid), len(grid[0]), 10**9
ways = [[0] * C for _ in range(R)]
cost = [[INF] * C for _ in range(R)]
came = [["."] * C for _ in range(R)]   # choice table: 'D' = from above, 'R' = from the left
for i in range(R):                     # row by row = a topological order of the cells
    for j in range(C):
        if grid[i][j] == "#":
            continue                   # closed crossing: 0 ways, infinite cost
        w = int(grid[i][j])
        if i == 0 and j == 0:
            ways[0][0], cost[0][0] = 1, w
            continue
        up = cost[i - 1][j] if i > 0 else INF
        left = cost[i][j - 1] if j > 0 else INF
        ways[i][j] = (ways[i - 1][j] if i > 0 else 0) + (ways[i][j - 1] if j > 0 else 0)
        if min(up, left) < INF:
            cost[i][j] = w + min(up, left)
            came[i][j] = "D" if up <= left else "R"    # tie: prefer coming from above
for i in range(R):
    a = " ".join(f"{x:2}" for x in ways[i])
    b = " ".join(f"{x:2}" if x < INF else " #" for x in cost[i])
    print(f"{a}     {b}     {' '.join(came[i])}")
print(f"paths: {ways[R - 1][C - 1]}  min cost: {cost[R - 1][C - 1]}")
i, j, moves, path = R - 1, C - 1, "", f"({R - 1},{C - 1})"
while i or j:                          # walk the choice table backwards
    moves = came[i][j] + moves
    if came[i][j] == "D":
        i -= 1
    else:
        j -= 1
    path = f"({i},{j}) " + path
print(f"moves: {moves}  path: {path}")

 1  1  1  1  1      3  5  9 10 12     . R R R R
 1  0  1  2  3      4  # 10 13 13     D . D D D
 1  1  2  0  3      6  7  9  # 15     D R R . D
 0  1  3  3  6      # 10 10 12 13     . D D R R
paths: 6  min cost: 13
moves: DDRRDRR  path: (0,0) (1,0) (2,0) (2,1) (2,2) (3,2) (3,3) (3,4)

৭ · DP মানে states-এর DAG-এ পথ — আর যেখানে DP ব্যর্থ

প্রতিটি DP-কে একটি গ্রাফ হিসেবে আঁকা যায়: প্রতিটি অবস্থা একটি vertex, আর “অবস্থা u-এর উত্তর অবস্থা v-এর হিসাবে লাগে” হলে একটি edge u → v. এটি অবস্থাগুলোর একটি DAG — cycle থাকলে কোনো অবস্থা নিজের ওপরই নির্ভর করত, আর হিসাব কখনো শুরু হতো না। গ্রিডে প্রতিটি মোড় একটি vertex, চালগুলো edge, ওজন মোড়ের জ্যাম; fib-এ k → k + 1 আর k → k + 2:

fib's state DAG: every k feeds k+1 and k+2

  edges k -> k+1 :  0 -> 1 -> 2 -> 3 -> 4 -> 5
  edges k -> k+2 :  0 -> 2,  1 -> 3,  2 -> 4,  3 -> 5

  6 vertices, 9 edges; the loop i = 2, 3, 4, 5 is a topological order

এভাবে দেখলে পর্ব ৪২-এর সাথে সম্পর্কটি পরিষ্কার: tabulation-এর লুপের ক্রম আসলে এই DAG-এর একটি topological order, আর memoization হলো DFS — DFS যেমন একটি vertex শেষ করার আগে তার সব প্রতিবেশী শেষ করে। Min-cost path হলো DAG-এ সংক্ষিপ্ততম পথ, পথ গোনা DAG-এ পথ গোনা, আর house robber-এ সর্বোচ্চ আয় একটি দীর্ঘতম পথ। DAG-এ এগুলো সব Θ(V + E) — আর DP-র “অবস্থা × transition” সূত্রটি ঠিক এই V + E.

যখন optimal substructure নেই — দীর্ঘতম simple path

এবার উল্টো উদাহরণ। চারটি শহর q, r, s, t, আর দুই দিকে চলা চারটি রাস্তা: q–r, r–t, t–s, s–q (একটি চতুর্ভুজ)। প্রশ্ন: q থেকে t পর্যন্ত সবচেয়ে লম্বা simple path (কোনো শহর দুবার নয়)। উত্তর ২টি রাস্তা — q → r → t বা q → s → t. এখন উপসমস্যা দেখুন। q থেকে r-এর দীর্ঘতম simple path হলো q → s → t → r (৩টি রাস্তা), আর r থেকে t-এর দীর্ঘতম r → q → s → t (৩টি)। দুটি জোড়া দিলে q → s → t → r → q → s → t — simple-ই নয়, শহরগুলো বারবার এসেছে।

সমস্যাটি হলো: উপসমস্যাগুলো স্বাধীন নয়। প্রথম অংশ যে শহরগুলো ব্যবহার করেছে, দ্বিতীয় অংশ সেগুলো আর ব্যবহার করতে পারে না — তাই “দুই অংশের সেরা” জুড়ে পুরো সেরা হয় না। সংক্ষিপ্ততম পথে এই সমস্যা হয় না, কারণ দুটি সংক্ষিপ্ততম অংশে কোনো শহর মিলে গেলে মাঝের লুপ কেটে আরও ছোট পথ পাওয়া যায় (cut-and-paste). দীর্ঘতম পথে লুপ কাটলে পথ ছোট হয় — যুক্তিটি উল্টো দিকে খাটে না। সাধারণ গ্রাফে দীর্ঘতম simple path আসলে NP-hard (পর্ব ৬৪), কারণ “n − 1 টি রাস্তার simple path আছে কি?” প্রশ্নটিই Hamiltonian path. DAG-এ (পর্ব ৪২) সমস্যা থাকে না, কারণ সেখানে প্রতিটি পথ নিজে থেকেই simple.

৮ · নামের গল্প, আর DP বনাম divide and conquer বনাম greedy

এই কোর্সের মডিউল ৭-এর তিনটি বড় কৌশল একই প্রশ্নের তিন উত্তর: “ছোট সমস্যা থেকে বড় সমাধান কীভাবে বানাব?”

একটি সহজ পরীক্ষা: ওভারটাইমের সমস্যায় greedy চেষ্টা করুন — “সবচেয়ে বেশি মজুরির দিনটি নাও, তার পাশের দুই দিন বাদ দাও, আবার করো”. a = [4, 5, 4]-এ greedy নেবে ৫ আর থামবে, অথচ সেরা উত্তর ৪ + ৪ = ৮. Greedy-র একটি পছন্দ ভবিষ্যতের সব পছন্দ বদলে দেয়, আর সে ফিরে দেখে না; DP দুটি পথই চেষ্টা করে সেরাটি রাখে। আবার যেখানে greedy প্রমাণসহ খাটে (পর্ব ৫০), সেখানে DP অপ্রয়োজনীয়ভাবে ধীর।

৯ · AI-এর যুগে DP — recurrence ঠিক, উত্তর ভুল

DP-র কোড AI সাধারণত ঝটপট লিখে দেয়, আর পরিচিত সমস্যায় (climbing stairs, house robber) প্রায়ই ঠিকও হয়। বিপদ আসে সামান্য বদলানো সমস্যায়: AI চেনা recurrence বসিয়ে দেয়, যদিও শর্ত বদলে গেছে; base case-এ একটি off-by-one; উত্তর dp[n]-এ খোঁজে, যখন আসলে সর্বোচ্চ মানটি দরকার; বা complexity বলে O(n), অথচ প্রতিটি অবস্থায় O(n) কাজ।

DP-তে AI সাধারণত যেসব ভুল করে

DP-র কোড যাচাইয়ের চেকলিস্ট

• অবস্থার সংজ্ঞা এক বাক্যে লিখেছি, আর কোডের প্রতিটি ঘর সেই সংজ্ঞাই মানে
• ছোট ইনপুটে টেবিলটি হাতে ভরে কোডের টেবিলের সাথে ঘরে ঘরে মিলিয়েছি
• সব সম্ভাবনা চেষ্টা করা একটি brute force লিখে শত শত এলোমেলো ছোট ইনপুটে মিলিয়েছি — stress testing
• Edge case: n = 0, n = 1, সব ঋণাত্মক, শুরু বা শেষের ঘর বন্ধ, এক সারি বা এক কলামের গ্রিড
• উত্তরের জায়গা ঠিক (dp[n], শেষ ঘর, নাকি সর্বোচ্চ), আর overflow-এর ঝুঁকি দেখেছি
• complexity = অবস্থা × transition নিজে গুনে AI-এর দাবির সাথে মিলিয়েছি