ডায়নামিক প্রোগ্রামিং — একই হিসাব দুবার নয়

১ · একই হিসাব দুবার কেন? — DP-র মূল ভাবনা

একটি পরিচিত দৃশ্য দিয়ে শুরু করি। ক্লাসে স্যার বোর্ডে লিখলেন: ১ + ১ + ১ + ১ + ১ + ১ + ১ + ১ = ? আপনি গুনে বললেন ৮. এবার স্যার বাঁ দিকে আরও একটি “১ +” যোগ করলেন। আপনি কি আবার শুরু থেকে গুনবেন? না — আপনি বলবেন “আগে ছিল ৮, আরেকটা যোগ হলো, তাহলে ৯.” আপনি আগের উত্তরটি মনে রেখেছিলেন, তাই নতুন করে গুনতে হয়নি।

এই সাধারণ বুদ্ধিটুকুই dynamic programming (সংক্ষেপে DP)-এর প্রাণ। নামটা ভারী শোনালেও ভেতরের কথাটি সহজ: যে হিসাব একবার করেছেন, সেটি আবার করবেন না — লিখে রাখুন।

পর্ব ১৫-এ recursion শেখার সময় আপনি দেখেছিলেন, fib(5)-এর মতো ছোট হিসাবেও একই fib(2) বারবার হিসাব হয়, আর memo টেবিল রাখলে ডাকের সংখ্যা অনেক কমে যায়। সেটি ছিল DP-র প্রথম ঝলক। আজ আমরা সেই ঝলককে একটি পূর্ণ কৌশলে পরিণত করব — যেটি দিয়ে টাকার হিসাব, ব্যাগ গোছানো, বানান শোধরানো, এমনকি GPS-এর পথ খোঁজার মতো সমস্যাও সমাধান হয়।

DP চেনার দুটি লক্ষণ

Divide & Conquer-এর সাথে পার্থক্য

পর্ব ৪০ আর ৪১-এ আপনি divide and conquer দেখেছেন — merge sort আর binary search-এ সমস্যাকে ভাগ করা হয়, ভাগগুলো আলাদাভাবে সমাধান হয়। DP-ও সমস্যা ভাগ করে। তাহলে পার্থক্য কোথায়? পার্থক্য হলো ভাগগুলো একে অপরের সাথে মেলে কি না।

২ · Fibonacci তিন উপায়ে — অপচয় থেকে দুটি ভ্যারিয়েবল

Fibonacci ধারা মনে করুন: 0, 1, 1, 2, 3, 5, 8, 13 … প্রতিটি সংখ্যা আগের দুটির যোগফল। সংজ্ঞাটি সরাসরি রিকার্শনে লেখা যায়: fib(n) = fib(n − 1) + fib(n − 2), আর base case fib(0) = 0, fib(1) = 1. সমস্যা হলো, এভাবে লিখলে একই কাজ অবিশ্বাস্য রকম বারবার হয়।

নিচের ডায়াগ্রামে একই প্রশ্ন — fib(5) — তিনভাবে সমাধান হচ্ছে। প্রথমে সরল রিকার্শন, তারপর memo টেবিলসহ রিকার্শন, তারপর নিচ থেকে টেবিল ভরা। প্রতিটি ধাপে ডান দিকের “হিসাব” অংশে কাজের পরিমাণ খেয়াল করুন:

চারটি পদ্ধতির তুলনা এক টেবিলে:

এবার নিজে মেপে দেখুন। নিচের কোডে সরল আর memo — দুই ভার্সনেই একটি counter আছে, যা গোনে ফাংশনটি মোট কতবার ডাকা হলো। শেষ লাইনে দুটি ভ্যারিয়েবল দিয়ে fib(90) বের করা হয়েছে:

#include <stdio.h>
long long calls = 0, memo[91];        /* memo[n] == 0 : not computed yet */
long long fib_naive(int n) {
    calls++; if (n <= 1) return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}
long long fib_memo(int n) {
    calls++; if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];          /* answer already written */
    long long x = fib_memo(n - 1);
    return memo[n] = x + fib_memo(n - 2);
}
int main(void) {
    long long r = fib_naive(32);
    printf("naive : fib(32) = %lld, calls = %lld\n", r, calls);
    calls = 0; r = fib_memo(32);
    printf("memo  : fib(32) = %lld, calls = %lld\n", r, calls);
    long long a = 0, b = 1;                    /* fib(0), fib(1) */
    for (int i = 0; i < 90; i++) { long long c = a + b; a = b; b = c; }
    printf("2 vars: fib(90) = %lld\n", a);
    return 0;
}

৩ · DP-র রেসিপি — পাঁচটি প্রশ্নের উত্তর লিখুন

Fibonacci সহজ, কারণ সূত্রটা আগেই দেওয়া। আসল সমস্যায় সূত্রটি আপনাকেই খুঁজে বের করতে হয়। অভিজ্ঞ প্রোগ্রামাররা কোড লেখার আগে খাতায় পাঁচটি প্রশ্নের উত্তর লেখেন। এই পাঁচটি পরিষ্কার হলে কোড প্রায় নিজে থেকেই লেখা হয়ে যায়।

Top-down নাকি bottom-up?

একই রেসিপি দুইভাবে কোডে বসানো যায়। দুটিই সমান “DP” — পার্থক্য শুধু কোন দিক থেকে হাঁটছেন।

৪ · Coin change — সবচেয়ে কম কয়েনে টাকা মেলানো

চায়ের দোকানে বসে আছেন। দোকানদারকে ১৮ টাকা ভাংতি ফেরত দিতে হবে। হাতে আছে ১, ২, ৫ টাকার কয়েন আর ১০ টাকার নোট — প্রতিটি যত খুশি। সবচেয়ে কম কয়টি কয়েন-নোটে ফেরত দেওয়া যায়? স্বাভাবিক বুদ্ধি বলে: সবচেয়ে বড়টা আগে নিন — ১০, তারপর ৫, তারপর ২, তারপর ১. মোট ৪টি। এই “এই মুহূর্তে সবচেয়ে বড়টা নিন” কৌশলকে বলে greedy, যা পরের পর্বে বিস্তারিত দেখবেন। বাংলাদেশের টাকার এই সেটে greedy সবসময় সঠিক উত্তর দেয়।

কিন্তু ধরুন কোনো এক দেশে কয়েন আছে শুধু ১, ৩ আর ৪ টাকার। ৬ টাকা মেলাতে হবে। Greedy নেবে প্রথমে ৪, বাকি ২ টাকা — ৩ নেওয়া যাবে না, তাই ১ + ১. মোট ৩টি কয়েন (৪ + ১ + ১)। অথচ ৩ + ৩ = ৬ — মাত্র ২টি কয়েনেই হয়! “এখনকার সেরা” বেছে নেওয়া সবসময় “সব মিলিয়ে সেরা” দেয় না। DP সব সম্ভাবনা গুছিয়ে দেখে, তাই কখনো ভুল করে না।

রেসিপি অনুযায়ী

• State: dp[x] = ঠিক x টাকা মেলাতে সবচেয়ে কম কয়টি কয়েন লাগে।
• Transition: x টাকা মেলানোর শেষ কয়েনটি কোনো একটি c টাকার কয়েন হবেই। তাহলে বাকি x − c টাকা আগেই সবচেয়ে কম কয়েনে মেলানো থাকতে হবে। তাই dp[x] = সব c-এর জন্য (dp[x − c] + 1)-এর মধ্যে সবচেয়ে ছোটটি।
• Base case: dp[0] = 0 — শূন্য টাকা মেলাতে কোনো কয়েন লাগে না।
• ক্রম: x = 1, 2, 3 … ছোট থেকে বড়, কারণ dp[x] সবসময় ছোট ঘর দেখে।
• উত্তর: dp[amount]; কোনোভাবেই মেলানো না গেলে −1.

এবার {১, ৩, ৪} কয়েন দিয়ে ৬ টাকার টেবিল ঘরে ঘরে ভরে দেখুন। প্রতিটি ঘরে তিনটি সম্ভাবনা যাচাই হচ্ছে — শেষ কয়েন ১, ৩ না ৪:

এই সমস্যার নাম coin change. নিচের কোডে ঠিক এই টেবিলটাই লুপ দিয়ে ভরা হয়েছে, আর তিনটি পরীক্ষা চালানো হয়েছে — বাংলাদেশের টাকা, {১, ৩, ৪}, আর এমন একটি সেট যেখানে মেলানোই অসম্ভব:

#include <stdio.h>
#define INF 1000000                       /* "not possible" marker */

int min_coins(const int coins[], int k, int amount) {
    int dp[amount + 1];                   /* dp[x] = fewest coins for x */
    dp[0] = 0;                            /* base case */
    for (int x = 1; x <= amount; x++) {
        dp[x] = INF;
        for (int j = 0; j < k; j++)
            if (coins[j] <= x && dp[x - coins[j]] + 1 < dp[x])
                dp[x] = dp[x - coins[j]] + 1;
    }
    return dp[amount] >= INF ? -1 : dp[amount];
}
int main(void) {
    int bd[] = {1, 2, 5, 10}, odd[] = {1, 3, 4}, big[] = {5, 10};
    printf("BD money, 18 : %d\n", min_coins(bd, 4, 18));
    printf("{1,3,4},   6 : %d\n", min_coins(odd, 3, 6));
    printf("{5,10},    7 : %d\n", min_coins(big, 2, 7));
    return 0;
}

৫ · 0/1 Knapsack — ঈদের বাসে ব্যাগ গোছানো

ঈদের আগে বাসে করে গ্রামের বাড়ি যাচ্ছেন। বাসের ছাদে জায়গা নেই, হাতে রাখা ব্যাগে বড়জোর ৬ কেজি নেওয়া যাবে। বাড়ির জন্য তিনটি জিনিস কেনা আছে, প্রতিটির ওজন আর পরিবারের কাছে তার “মূল্য-পয়েন্ট” আলাদা:

প্রতিটি জিনিস হয় পুরো নেবেন, নয়তো নেবেনই না — অর্ধেক রাইস কুকার নেওয়া যায় না। তাই নাম “0/1”. “প্রতি কেজিতে সবচেয়ে দামি আগে” — এই greedy নিয়মে প্রথমে রাইস কুকার (৪ কেজি) উঠবে, বাকি ২ কেজিতে আর কিছুই ধরবে না: মোট ৭. অথচ শাড়ি-পাঞ্জাবি আর জামা মিলে ৬ কেজি, মূল্য ৯! এই সমস্যার নাম knapsack (knapsack মানে পিঠের ঝোলা)।

• State: K[i][c] = প্রথম i টি জিনিস থেকে বেছে, c কেজির ব্যাগে সর্বোচ্চ কত মূল্য নেওয়া যায়।
• Transition: i-তম জিনিসটির জন্য মাত্র দুটি পথ। না নিলে: K[i − 1][c]. নিলে (যদি ওজন w ≤ c হয়): K[i − 1][c − w] + মূল্য। দুটির মধ্যে বড়টি।
• Base case: কোনো জিনিস না থাকলে (i = 0) সব ঘর 0.
• ক্রম: সারি ধরে ওপর থেকে নিচে; প্রতিটি সারি শুধু ঠিক ওপরের সারি দেখে।
• উত্তর: সবচেয়ে নিচের সারির শেষ ঘর, K[3][6].

এক সারির array — লুপের দিক কেন গুরুত্বপূর্ণ

প্রতিটি সারি শুধু ঠিক ওপরের সারি দেখে। তাহলে পুরো 2D টেবিল না রেখে একটিই 1D array best[c] রেখে সেটিকেই বারবার হালনাগাদ করা যায়। কিন্তু এখানে একটি ফাঁদ আছে, যেটি AI-এর কোডেও প্রায়ই দেখা যায়:

for (int i = 0; i < n; i++)
    for (int c = W; c >= w[i]; c--)          /* right to left */
        if (best[c - w[i]] + v[i] > best[c])
            best[c] = best[c - w[i]] + v[i];

for (int i = 0; i < n; i++)
    for (int c = w[i]; c <= W; c++)          /* left to right */
        if (best[c - w[i]] + v[i] > best[c])
            best[c] = best[c - w[i]] + v[i];

৬ · দুটি লেখার তুলনা — LCS ও edit distance

ফোনে কাউকে লিখছেন “আমি sylhet যাচ্ছি”, কিন্তু তাড়াহুড়োয় টাইপ হলো “silet”. Keyboard সঙ্গে সঙ্গে নিচে পরামর্শ দেখায়: “Sylhet?” সে কীভাবে বুঝল আপনি আসলে কোন শব্দটি চেয়েছিলেন? এর একটি মূল উপাদান হলো দুটি শব্দের মধ্যে “দূরত্ব” মাপা: একটি থেকে আরেকটিতে যেতে সবচেয়ে কম কয়টি পরিবর্তন লাগে।

পরিবর্তন তিন রকম: একটি অক্ষর ঢোকানো (insert), মুছে ফেলা (delete), অথবা বদলে দেওয়া (substitute). সবচেয়ে কম পরিবর্তনের সংখ্যাকে বলে edit distance — একে Levenshtein distance-ও বলে, সোভিয়েত গণিতবিদ Vladimir Levenshtein-এর নামে, যিনি ১৯৬০-এর দশকে এটি নিয়ে কাজ করেন।

• State: D[i][j] = প্রথম শব্দের প্রথম i টি অক্ষরকে দ্বিতীয় শব্দের প্রথম j টি অক্ষরে বদলাতে সবচেয়ে কম কয়টি পরিবর্তন লাগে।
• Transition: শেষ দুটি অক্ষর মিললে কিছুই করতে হয় না: D[i][j] = D[i − 1][j − 1]. না মিললে তিন রাস্তার সবচেয়ে সস্তাটি + 1 — মুছুন (ওপরের ঘর), ঢোকান (বাঁয়ের ঘর), বা বদলান (কোনাকুনি ঘর)।
• Base case: খালি লেখা থেকে j অক্ষর বানাতে j বার ঢোকাতে হয়: D[0][j] = j. একইভাবে D[i][0] = i.
• উত্তর: একদম নিচের ডান কোণের ঘর।

LCS — দুটি লেখায় সবচেয়ে লম্বা মিল

Edit distance-এর খুব কাছের আত্মীয় হলো longest common subsequence বা LCS: দুটি লেখা থেকে কিছু অক্ষর বাদ দিয়ে (ক্রম না বদলে) সবচেয়ে লম্বা কোন অংশটি দুটিতেই পাওয়া যায়? sylhet আর silet-এর LCS হলো “slet” — ৪টি অক্ষর। এর টেবিলও একই রকম গ্রিড: অক্ষর মিললে কোনাকুনি ঘর + 1, না মিললে ওপর আর বাঁয়ের মধ্যে বড়টি।

LCS জানলে অনেক কিছু জানা যায়। যেমন, শুধু ঢোকানো আর মোছার অনুমতি থাকলে পরিবর্তন লাগে (৬ + ৫) − ২ × ৪ = ৩টি: y আর h মুছুন, i ঢোকান। আরও বড় ব্যবহার হলো ফাইলের তুলনা। দুটি ফাইলের লাইনগুলোকে অক্ষর ধরে LCS বের করলে যে লাইনগুলো LCS-এ নেই, সেগুলোই “বদলেছে”। ১৯৭০-এর দশকে Unix-এর diff প্রোগ্রাম এই প্রশ্নের ওপর দাঁড়িয়েই তৈরি হয়েছিল, আর আজ আপনি যখন git diff-এ লাল-সবুজ লাইন দেখেন, তার পেছনেও একই প্রশ্ন — যদিও git আরও দ্রুত, বিশেষ অ্যালগরিদম ব্যবহার করে।

৭ · বাস্তবে DP কোথায় কাজ করে

DP কোনো প্রতিযোগিতার কৌশল মাত্র নয়। আপনার ফোন, ইন্টারনেট আর AI-এর ভেতরে প্রতিদিন কোটি কোটি বার এটি চলছে। কয়েকটি উদাহরণ:

Bellman equation-এর ভাবটি সহজ বাংলায় বলা যায়: “এই অবস্থার মূল্য = এখনই পাওয়া পুরস্কার + পরের অবস্থার মূল্য (একটু কমিয়ে ধরা)।” ঠিক coin change-এর মতো — dp[x]-কে প্রকাশ করা হয়েছিল ছোট একটি ঘর দিয়ে। পার্থক্য হলো, এখানে “ঘর” মানে দাবার একটি অবস্থান বা রোবটের একটি অবস্থান, আর ঘরের সংখ্যা এত বেশি যে পুরো টেবিল লেখা অসম্ভব। তখন টেবিলের বদলে একটি neural network সেই মান অনুমান করে। কিন্তু ভেতরের চিন্তা Bellman-এর ১৯৫০-এর দশকের DP-ই।

৮ · AI-এর যুগে DP — সুন্দর কোড, লুকানো ভুল

AI-কে “coin change-এর C কোড দাও” বললে কয়েক সেকেন্ডে ঝকঝকে কোড পাবেন। DP কোড ছোট আর দেখতে নিরীহ, তাই চোখ বুলিয়ে মনে হয় ঠিকই আছে। কিন্তু DP-র ভুল সাধারণত crash করে না — চুপচাপ একটি ভুল সংখ্যা দেয়। আর সেই সংখ্যা প্রায়ই “বিশ্বাসযোগ্য” দেখায়।

AI-এর DP কোডে যেসব ভুল বেশি দেখা যায়

এসব ভুল ধরার সবচেয়ে শক্তিশালী উপায় একটি পুরোনো কৌশল: brute force-এর সাথে মেলানো। ছোট ইনপুটে (যেমন amount ≤ 20) সব সম্ভাব্য সমন্বয় একে একে চেষ্টা করে এমন একটি ধীর কিন্তু নিশ্চিতভাবে সঠিক ফাংশন লিখুন। তারপর কয়েকশো এলোমেলো ছোট ইনপুটে দুটির উত্তর মিলিয়ে দেখুন। একটিও না মিললে DP-তে ভুল আছে — আর কোন ইনপুটে মেলেনি, সেটিই আপনার test case.

AI-এর DP কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• dp-র একটি ঘরের অর্থ নিজের ভাষায় এক বাক্যে বলতে পারি
• Base case-গুলো (0, 1, খালি লেখা) হাতে হিসাব করে মিলিয়েছি
• প্রতিটি ঘর ভরার সময় যে ঘরগুলো পড়া হচ্ছে, সেগুলো আগেই ভরা — লুপের ক্রম যাচাই করেছি
• টেবিলের আকার n + 1 কি না, আর কোনো index array-র বাইরে যায় কি না দেখেছি
• অসম্ভব ইনপুট আর সবচেয়ে বড় ইনপুট — দুটোতেই চালিয়েছি
• ছোট ইনপুটে brute force-এর সাথে অনেকবার মিলিয়েছি