DP-র ক্লাসিক সমস্যা ১ — knapsack, coin change আর LIS

১ · সমস্যা — ঈদের ব্যাগ, ৭ কেজির সীমা আর greedy-র ফাঁদ

ঈদে বাড়ি যাচ্ছেন। বাসের কোম্পানি বলে দিয়েছে, যাত্রীপ্রতি মালপত্র সর্বোচ্চ ৭ কেজি। ঘরে চারটি জিনিস প্রস্তুত, প্রতিটির একটি ওজন আর একটি “দরকারের নম্বর” (মান) আছে — যত বেশি নম্বর, বাড়িতে সেটি তত কাজে লাগবে:

জিনিস ভেঙে অর্ধেক নেওয়া যায় না — উপহার হয় পুরোটা যাবে, নয়তো যাবে না। প্রতিটি জিনিসের জন্য সিদ্ধান্ত মাত্র দুটি: নেব (১) বা নেব না (০). তাই এর নাম 0/1 knapsack (knapsack মানে পিঠের ব্যাগ)। লক্ষ্য: মোট ওজন ৭ কেজির মধ্যে রেখে মোট মান সবচেয়ে বেশি করা।

প্রথম চিন্তা আসে greedy (পর্ব ৫০): প্রতি কেজিতে যার মান সবচেয়ে বেশি, তাকে আগে নিন। মিষ্টির বাক্স (১.৪০) নিলাম — ৫ কেজি, বাকি ২ কেজি। উপহার (৩ কেজি) বা জামা (৪ কেজি) আর ধরে না, শুধু চানাচুর ঢোকে। মোট মান ৭ + ১ = ৮. কিন্তু উপহার আর জামা একসাথে নিলে ওজন ঠিক ৭, মান ৪ + ৫ = ৯ — greedy-র চেয়ে ভালো। এটি একটি counterexample: greedy এখানে ভুল। জিনিস ভাঙা গেলে (চাল, তেল — fractional knapsack) সেই greedy-ই সেরা, পর্ব ৫০-এ তার প্রমাণ আছে; ভাঙা না গেলে বাক্সের ফাঁকা জায়গা নষ্ট হয়, আর সেই হিসাব greedy করতে পারে না।

আরেকটি উপায় brute force: প্রতিটি জিনিস নেওয়া-না-নেওয়ার সব 2ⁿ টি সমন্বয় পরীক্ষা। n = 4-এ ১৬টি — সহজ। কিন্তু n = 100-এ 2¹⁰⁰ — exponential time, মহাবিশ্বের বয়সেও শেষ হবে না। পর্ব ৫২-এ (Dynamic programming-এর ভিত্তি) দেখেছেন, dynamic programming কাজ করে যখন সমস্যার optimal substructure আছে আর সরল recursion-এ একই উপসমস্যা বারবার আসে (overlapping subproblems). এই পর্বে সেই কাঠামো চারটি ক্লাসিক সমস্যায় প্রয়োগ করব — প্রতিটিতে একই চারটি প্রশ্ন: state কী, transition কী, base case কী, আর কোন ক্রমে টেবিল ভরব।

২ · 0/1 knapsack-এর state আর transition — dp[i][w]

State. একটি উপসমস্যাকে চেনাতে দুটি সংখ্যা যথেষ্ট: কতগুলো জিনিস নিয়ে ভাবছি আর ব্যাগে কত জায়গা আছে। তাই state:

Transition. জিনিস i-কে নিয়ে মাত্র দুটি সম্ভাবনা। না নিলে প্রথম i − 1 টি জিনিস দিয়ে ক্ষমতা w-এর সেরা উত্তর: dp[i−1][w]. নিলে (যদি wᵢ ≤ w) তার মান vᵢ, আর বাকি w − wᵢ জায়গায় প্রথম i − 1 টির সেরা উত্তর। দুটির বড়টিই উত্তর — এটিই transition:

Base case. কোনো জিনিস না থাকলে মান 0: dp[0][w] = 0 সব w-এ। ক্রম. সারি i ভরতে শুধু সারি i − 1 লাগে, তাই সারি ধরে ওপর থেকে নিচে। উত্তর dp[n][W].

কেন ঠিক. i-এর ওপর induction. ধরুন সারি i − 1-এর সব ঘর সঠিক। প্রথম i টি জিনিস থেকে ক্ষমতা w-এর একটি সেরা ব্যাগ S নিন। S-এ জিনিস i না থাকলে S আসলে প্রথম i − 1 টির একটি বৈধ ব্যাগ, তাই মান(S) ≤ dp[i−1][w]. থাকলে S থেকে i সরালে প্রথম i − 1 টির একটি ব্যাগ পাওয়া যায় যার ওজন ≤ w − wᵢ, তাই মান(S) − vᵢ ≤ dp[i−1][w − wᵢ]. অর্থাৎ max-এর দুটি পদের একটি অন্তত মান(S)-এর সমান। উল্টো দিকে, max-এর প্রতিটি পদ একটি বাস্তব বৈধ ব্যাগের মান, তাই সেরার চেয়ে বেশি হতে পারে না। দুটি মিলে dp[i][w] = মান(S). ∎ লক্ষ করুন, “i একবারই নেওয়া যায়” শর্তটি এসেছে dp[i−1][…]-এর i − 1 থেকে — নেওয়ার পরও আমরা আগের সারিতে যাই।

Pseudocode — 0/1 knapsack (items 1..n, capacities 0..W)

for w = 0 to W:  dp[0][w] = 0
for i = 1 to n:
    for w = 0 to W:
        dp[i][w] = dp[i-1][w]                              // skip item i
        if wt[i] <= w:
            dp[i][w] = max(dp[i][w], dp[i-1][w - wt[i]] + val[i])   // take item i once
return dp[n][W]

ঈদের ব্যাগে টেবিলটি সারি ধরে ভরা দেখুন। কলাম w = 0 থেকে 7, সারি i = 0 থেকে 4:

খরচ. টেবিলে (n + 1)(W + 1) টি ঘর, প্রতিটি O(1)-এ — সময় ও জায়গা Θ(nW).

৩ · কোন জিনিস নিলাম — reconstruction, আর এক সারির DP-তে উল্টো লুপ

উত্তরের সংখ্যাটি (9) জানাই যথেষ্ট নয়; ব্যাগে কী ঢোকাব, সেটিও চাই। ডায়াগ্রামের শেষ দুই ধাপে যা করলেন, সেটিই নিয়ম: i = n, w = W থেকে শুরু করে প্রতিটি i-তে dp[i][w] ≠ dp[i−1][w] হলে জিনিস i নেওয়া হয়েছে (তখন w থেকে wᵢ বাদ), নইলে নেওয়া হয়নি। কারণ dp[i][w] হয় dp[i−1][w], নয়তো dp[i−1][w − wᵢ] + vᵢ — মান বদলালে দ্বিতীয়টিই জিতেছে। এটি গ্রাফে parent ধরে পথ ফেরত আনার (path reconstruction, পর্ব ৪৩) মতোই; খরচ মাত্র O(n), তবে পুরো দুই-মাত্রার টেবিল রেখে দিতে হয়।

এক সারির DP — জায়গা Θ(W)

শুধু সর্বোচ্চ মান চাইলে পুরো টেবিল রাখার দরকার নেই: সারি i বানাতে শুধু সারি i − 1 লাগে। আরও এক ধাপ এগিয়ে একটিমাত্র অ্যারে one[0..W] রাখা যায়, যেখানে নতুন মান পুরোনোর জায়গায় লেখা হয়। কিন্তু একটি সূক্ষ্ম বিষয় আছে। one[w] হিসাব করতে লাগে পুরোনো সারির one[w − wᵢ]. w − wᵢ < w, তাই w-কে বড় থেকে ছোট দিকে চালালে one[w − wᵢ] তখনো ছোঁয়া হয়নি — পুরোনো মানই আছে। ছোট থেকে বড় দিকে চালালে one[w − wᵢ] এই সারিতেই একবার বদলে গেছে, মানে তাতে জিনিস i হয়তো আগেই ঢুকেছে — আর তার ওপর আবার vᵢ যোগ করলে একই জিনিস দুবার:

ভুল পথের ধাপটি কিন্তু অন্য এক সমস্যার সঠিক সমাধান: যদি প্রতিটি জিনিস যতবার খুশি নেওয়া যেত (unbounded knapsack), তাহলে one[w − wᵢ]-এ জিনিস i আগেই থাকাটাই আমরা চাইতাম। উল্টো লুপ = প্রতিটি জিনিস একবার, সামনের লুপ = যতবার খুশি — এক লাইনের পার্থক্য, সম্পূর্ণ ভিন্ন সমস্যা। এক সারির DP-তে জায়গা Θ(W), সময় তবুও Θ(nW); কিন্তু জিনিসের তালিকা ফেরত পেতে আলাদা ব্যবস্থা লাগে (যেমন প্রতিটি সারির জন্য একটি bit রাখা: “এই w-এ জিনিস i নিয়েছি কি না”).

নিচের প্রোগ্রাম দুই-মাত্রার টেবিল ভরে, পেছনে হেঁটে জিনিসের তালিকা বের করে, তারপর এক সারির উল্টো-লুপ সংস্করণ চালিয়ে মিলিয়ে দেখে — এক সারির অ্যারে কি প্রতিটি ক্ষমতায় দুই-মাত্রার শেষ সারির সমান?

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    vector<string> names{"snacks", "gifts", "clothes", "sweets"};
    vector<int> wt{1, 3, 4, 5};                       // weight in kg
    vector<int> val{1, 4, 5, 7};                      // how much we need it
    const int n = 4, W = 7;
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));   // dp[i][w]: first i items, capacity w
    for (int i = 1; i <= n; ++i)
        for (int w = 0; w <= W; ++w) {
            dp[i][w] = dp[i - 1][w];                  // skip item i
            if (wt[i - 1] <= w)                       // or take it (once)
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
        }
    vector<int> taken;                                // walk back from dp[n][W]
    for (int i = n, w = W; i >= 1; --i)
        if (dp[i][w] != dp[i - 1][w]) { taken.push_back(i); w -= wt[i - 1]; }
    reverse(taken.begin(), taken.end());
    vector<int> one(W + 1, 0);                        // the same DP in one row
    for (int i = 0; i < n; ++i)
        for (int w = W; w >= wt[i]; --w)              // reverse: each item used at most once
            one[w] = max(one[w], one[w - wt[i]] + val[i]);
    cout << "best value: " << dp[n][W] << '\n' << "take:";
    int total = 0;
    for (int i : taken) { cout << ' ' << i << ':' << names[i - 1]; total += wt[i - 1]; }
    cout << " weight " << total << '\n' << "2D last row:";
    for (int x : dp[n]) cout << ' ' << x;
    cout << '\n' << "1D row     :";
    for (int x : one) cout << ' ' << x;
    cout << '\n' << "1D == 2D for every capacity: " << (one == dp[n] ? "yes" : "no") << '\n';
}

best value: 9
take: 2:gifts 3:clothes weight 7
2D last row: 0 1 1 4 5 7 8 9
1D row     : 0 1 1 4 5 7 8 9
1D == 2D for every capacity: yes

names = ["snacks", "gifts", "clothes", "sweets"]
wt  = [1, 3, 4, 5]                               # weight in kg
val = [1, 4, 5, 7]                               # how much we need it
n, W = len(wt), 7

dp = [[0] * (W + 1) for _ in range(n + 1)]       # dp[i][w]: best value, first i items, capacity w
for i in range(1, n + 1):
    for w in range(W + 1):
        dp[i][w] = dp[i - 1][w]                  # skip item i
        if wt[i - 1] <= w:                       # or take it (once)
            dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])

taken, w = [], W                                 # walk back from dp[n][W]
for i in range(n, 0, -1):
    if dp[i][w] != dp[i - 1][w]:                 # value changed: item i was taken
        taken.append(i); w -= wt[i - 1]
taken.reverse()

one = [0] * (W + 1)                              # the same DP in one row
for i in range(n):
    for w in range(W, wt[i] - 1, -1):            # reverse: each item used at most once
        one[w] = max(one[w], one[w - wt[i]] + val[i])

print("best value:", dp[n][W])
print("take:", " ".join(f"{i}:{names[i - 1]}" for i in taken),
      "weight", sum(wt[i - 1] for i in taken))
print("2D last row:", *dp[n])
print("1D row     :", *one)
print("1D == 2D for every capacity:", "yes" if one == dp[n] else "no")

best value: 9
take: 2:gifts 3:clothes weight 7
2D last row: 0 1 1 4 5 7 8 9
1D row     : 0 1 1 4 5 7 8 9
1D == 2D for every capacity: yes

৪ · O(nW) কেন “প্রায়” polynomial — pseudo-polynomial সময়

Θ(nW) দেখে মনে হয় এটি একটি সাধারণ polynomial অ্যালগরিদম — n আর W-এর গুণফল। অথচ পর্ব ৬৪-এ দেখবেন, knapsack-এর সিদ্ধান্ত-রূপ (“মান ≥ K করা যায় কি?”) NP-complete — Richard Karp ১৯৭২ সালে যে ২১টি সমস্যাকে NP-complete দেখান, তার একটি knapsack. তাহলে কি আমরা P = NP প্রমাণ করে ফেললাম? না। কারণটি লুকিয়ে আছে “ইনপুটের আকার” (input size) কথাটির মধ্যে।

Complexity মাপা হয় ইনপুট লিখতে কত bit লাগে তার সাপেক্ষে। n টি জিনিস লিখতে n টি সংখ্যা লাগে, কিন্তু W সংখ্যাটি লিখতে লাগে মাত্র b = ⌈log₂(W + 1)⌉ টি bit. W = 10¹⁸ লিখতে ৬০ bit — ইনপুটে একটি ছোট সংখ্যা মাত্র। অথচ টেবিলে W + 1 টি কলাম, অর্থাৎ প্রায় 2^b. তাই সময় O(n · 2^b) — ইনপুটের দৈর্ঘ্যে exponential. W-এ একটি অঙ্ক (bit) বাড়ালে সময় দ্বিগুণ হয়। এমন সময়কে বলে pseudo-polynomial: সংখ্যাগুলোর মানে polynomial, কিন্তু তাদের দৈর্ঘ্যে নয়।

ব্যবহারিক সিদ্ধান্ত সহজ: কনটেস্ট বা বাস্তব সমস্যায় আগে সীমাগুলো দেখুন। n·W মোটামুটি 10⁸-এর মধ্যে হলে এই DP. W বিশাল কিন্তু মানগুলো ছোট হলে উল্টো state নিন — dp[v] = মান ঠিক v পেতে সবচেয়ে কম ওজন — সময় O(n·V), V = মোট মান; উত্তর হলো সবচেয়ে বড় v, যার dp[v] ≤ W. দুটোই বিশাল কিন্তু n ছোট (≤ ৪০) হলে meet in the middle (অংশ ৯-এর “আরও গভীরে”). Pseudo-polynomial সময় তাই NP-complete সমস্যার একটি “দুর্বল জায়গা”: সংখ্যাগুলো ছোট থাকলে সমস্যাটি আসলে সহজ। এমন সমস্যাকে বলা হয় weakly NP-hard; যেগুলো ছোট সংখ্যাতেও কঠিন থাকে (যেমন traveling salesman, পর্ব ৫৭), সেগুলো strongly NP-hard.

৫ · একই ছাঁচের আরও সমস্যা — unbounded, subset sum, partition আর bounded knapsack

Unbounded knapsack — সামনের লুপ

একটি পাইকারি দোকানে বস্তা ভরছেন: চিনির ১ কেজির প্যাকেট, ডালের ৩ কেজির প্যাকেট — প্রতিটি যতগুলো খুশি। এখানে state হতে পারে একটিই সংখ্যা: dp[w] = ক্ষমতা w-এ সর্বোচ্চ মান, আর dp[w] = max over i ( dp[w − wᵢ] + vᵢ ). অংশ ৩-এর ভাষায়, এক সারির DP-তে w-এর লুপ সামনে থেকে:

Pseudocode — unbounded knapsack (each item any number of times)

dp[0..W] = 0
for each item i:
    for w = wt[i] to W:                       // forward: dp[w - wt[i]] may already contain item i
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
return dp[W]

সময় Θ(nW), জায়গা Θ(W). এখানে লুপ দুটির ক্রম উল্টে দিলেও (w বাইরে, i ভেতরে) সর্বোচ্চ মান একই আসে, কারণ max-এ ক্রম গুরুত্বহীন — কিন্তু অংশ ৬-এ দেখবেন, “কত উপায়ে” গুনতে গেলে ক্রমই সব।

Subset sum আর partition — হ্যাঁ/না-এর DP

কয়েকটি সংখ্যা দেওয়া আছে; এদের কোনো উপসেটের যোগফল ঠিক S হতে পারে কি? এটি subset sum — knapsack-এর বিশেষ রূপ, যেখানে মান = ওজন, আর আমরা শুধু জানতে চাই একটি নির্দিষ্ট যোগফল “পৌঁছানো যায় কি না”. state: can[s] = এখন পর্যন্ত দেখা সংখ্যা দিয়ে যোগফল s বানানো যায় কি না। শুরুতে শুধু can[0] = সত্য। প্রতিটি সংখ্যা x-এর জন্য s = S থেকে x পর্যন্ত (উল্টো লুপ — প্রতিটি সংখ্যা একবার): can[s] = can[s] OR can[s − x]. সময় O(n·S).

উদাহরণ {2, 3, 7, 8}: পৌঁছানো যায় এমন যোগফলের সেট ধাপে ধাপে বাড়ে — শুরুতে {0}; 2 নিয়ে {0, 2}; 3 নিয়ে {0, 2, 3, 5}; 7 নিয়ে {0, 2, 3, 5, 7, 9, 10, 12}; 8 নিয়ে আরও বাড়ে। মোট যোগফল 20, আর 10 পৌঁছানো যায় — তাই সংখ্যাগুলোকে সমান যোগফলের দুই দলে ভাগ করা যায়: {3, 7} আর {2, 8}. এই প্রশ্নটিই partition problem: মোট যোগফল T জোড় হলে T/2-এর subset sum; বিজোড় হলে সরাসরি “না”. দুই ভাইয়ের মধ্যে জমি বা দুই ট্রাকে মাল সমান ভাগের প্রশ্ন এভাবেই আসে।

লক্ষ করুন, প্রতিটি ধাপ আসলে “পুরোনো সেট OR (পুরোনো সেট x ঘর সরানো)”. সেটটিকে একটি bitset-এ রাখলে পুরো ধাপটি এক লাইনে: bits |= bits << x;. প্রসেসর একসাথে ৬৪টি bit সরায়, তাই সময় O(n·S / 64) — কনটেস্টে S ≈ 10⁶-এর subset sum এভাবেই পার হয়।

Bounded knapsack — binary splitting

মাঝামাঝি রূপ: জিনিস i সর্বোচ্চ cᵢ বার নেওয়া যায় (যেমন দোকানে মিষ্টির প্যাকেট আছে মাত্র ১৩টি) — bounded knapsack. সরল উপায়ে ১৩টিকে ১৩টি আলাদা 0/1 জিনিস ধরলে সময় O(W · Σcᵢ). চতুর উপায় binary splitting: ১৩টি প্যাকেটকে 1, 2, 4 আর বাকি 6 আকারের চারটি বান্ডিলে ভাগ করুন, প্রতিটি বান্ডিল একটি 0/1 জিনিস (ওজন ও মান বান্ডিলের আকার দিয়ে গুণ)। 0 থেকে 13-এর যেকোনো সংখ্যা এই বান্ডিলগুলোর কিছুর যোগফল (যেমন 11 = 1 + 4 + 6, 13 = 1 + 2 + 4 + 6), আর 13-এর বেশি কখনো হয় না। তাই উত্তর একই থাকে, কিন্তু জিনিস মাত্র প্রায় log₂ cᵢ টি — সময় O(W · Σ log cᵢ). (monotonic deque দিয়ে O(nW)-ও সম্ভব, পর্ব ১৬-এর sliding window-এর ধারণায়; কনটেস্টে binary splitting-ই বেশি লেখা হয়।)

৬ · Coin change — সবচেয়ে কম কয়েন আর কত উপায়ে

ধরুন একটি দেশে কয়েন শুধু 1, 3 আর 4 টাকার। দোকানিকে ৬ টাকা ফেরত দিতে হবে। এটি coin change, আর এর দুটি প্রশ্ন আছে: (১) সবচেয়ে কম কয়টি কয়েন লাগবে? (২) মোট কত উপায়ে ৬ টাকা বানানো যায়? প্রতিটি কয়েন যতবার খুশি — তাই দুটিই unbounded knapsack-এর আত্মীয়।

প্রশ্ন ১ — সবচেয়ে কম কয়েন

Greedy: সবচেয়ে বড় যে কয়েন চলে, সেটি দিন — 4, তারপর 1, 1: তিনটি কয়েন। কিন্তু 3 + 3 = দুটি কয়েন। আবার greedy ভুল। DP: best[a] = অঙ্ক a বানাতে সবচেয়ে কম কয়েন, best[0] = 0, আর best[a] = 1 + min over কয়েন c ≤ a ( best[a − c] ) — শেষ কয়েনটি কোনটি, তা সব রকম চেষ্টা। a = 0 থেকে বাড়তি ক্রমে:

amount a : 0  1  2  3  4  5  6
best[a]  : 0  1  2  1  1  2  2      best[6] = 1 + min(best[5], best[3], best[2]) = 1 + 1 = 2  (3 + 3)

যে অঙ্ক বানানোই যায় না (যেমন শুধু 5 আর 7-এর কয়েনে 3), সেখানে best = ∞ রাখুন, আর শেষে ∞ হলে “অসম্ভব” বলুন। সময় O(k·A), k = কয়েনের ধরন, A = অঙ্ক — এটিও pseudo-polynomial. বাস্তবের মুদ্রা (1, 2, 5, 10-এর ধাঁচ) এমনভাবে বানানো যে সেখানে greedy সব সময় সেরা — এমন ব্যবস্থাকে বলে canonical coin system. কিন্তু কোনো ব্যবস্থা canonical কি না, না জেনে greedy চালানো বিপদ।

প্রশ্ন ২ — কত উপায়ে, আর লুপের ক্রম

“কত উপায়ে” প্রশ্নে প্রথমে ঠিক করুন, 1 + 1 + 4 আর 4 + 1 + 1 একই উপায় কি না। দোকানে ফেরত দেওয়ার হিসাবে একই — শুধু কোন কয়েন কয়টি, সেটিই গুরুত্বপূর্ণ (combination). কিন্তু সিঁড়িতে ১, ৩ বা ৪ ধাপে লাফ দিয়ে ৬ ধাপ ওঠার প্রশ্নে লাফের ক্রম আলাদা হলে পথও আলাদা (ক্রমসহ গোনা). দুটির কোড প্রায় একই — শুধু দুই লুপের কোনটি বাইরে:

Pseudocode — number of ways (ways[0] = 1, all others 0)

// (A) order does NOT matter: coins outside
for each coin c:
    for a = c to A:  ways[a] += ways[a - c]

// (B) order matters: amounts outside
for a = 1 to A:
    for each coin c <= a:  ways[a] += ways[a - c]

(A)-তে কয়েনগুলো একটি একটি করে “চালু” হয়: প্রথম কয়েনের ধাপ শেষে ways[a] = শুধু সেই কয়েন দিয়ে উপায়, দ্বিতীয়টির পর = প্রথম দুটি দিয়ে, ইত্যাদি। প্রতিটি সমন্বয় ঠিক একবার গোনা হয় — কয়েনগুলো সব সময় একই নির্দিষ্ট ক্রমে যোগ হয় বলে (আগে সব 1, তারপর সব 3, তারপর সব 4). (B)-তে প্রতিটি অঙ্কে “শেষ কয়েনটি কোনটি” সব রকম চেষ্টা হয়, তাই 1 + 1 + 4 আর 4 + 1 + 1 আলাদা শেষ কয়েনে দুবার গোনা হয়:

দুই সংস্করণই O(k·A) সময় আর O(A) জায়গা। উপায়ের সংখ্যা খুব দ্রুত বড় হয় (A = 1000-এ প্রায়ই 64-bit-এরও বাইরে), তাই প্রশ্নে সাধারণত “উত্তর mod 10⁹ + 7” চাওয়া হয় — প্রতিটি যোগের পর mod নিন। এখানে আরেকটি গভীর মিল আছে: (B)-র ways[a] আসলে একটি DAG-এ 0 থেকে a পর্যন্ত পথের সংখ্যা (প্রতিটি অঙ্ক একটি node, প্রতিটি কয়েন একটি edge) — পর্ব ৪২-এর topological order-এ পথ গোনা। প্রায় প্রতিটি DP-কে এভাবে state-এর একটি DAG হিসেবে দেখা যায়।

৭ · LIS — সবচেয়ে লম্বা বাড়তে থাকা subsequence, O(n²) DP

একজন ব্যাটারের পরপর আটটি ম্যাচের রান (দশকে): 3 1 4 1 5 9 2 6. আমরা খুঁজছি সবচেয়ে লম্বা এমন ম্যাচ-তালিকা (ক্রম বজায় রেখে, মাঝে কিছু বাদ দেওয়া চলবে), যেখানে প্রতিটি ম্যাচে রান আগেরটির চেয়ে কঠোরভাবে বেশি — “উন্নতির সবচেয়ে লম্বা ধারা”. ক্রম থেকে কিছু উপাদান বাদ দিয়ে, বাকিদের ক্রম না বদলে যা থাকে, তাকে বলে subsequence (পাশাপাশি থাকার দরকার নেই — পাশাপাশি হলে বলে subarray). সমস্যাটির নাম longest increasing subsequence (LIS). এখানে উত্তর 4 — যেমন 1 4 5 6 বা 3 4 5 9. পাঁচটির কোনো বাড়তি ধারা নেই।

State. dp[i] = ঠিক a[i]-তে শেষ হওয়া সবচেয়ে লম্বা বাড়তি subsequence-এর দৈর্ঘ্য। “শেষ হওয়া” শর্তটিই চাবি: এতে জানা থাকে শেষ উপাদানটি কত, তাই নতুন উপাদান জোড়া যায় কি না বলা যায়। Transition: dp[i] = 1 + max{ dp[j] : j < i এবং a[j] < a[i] } (এমন j না থাকলে dp[i] = 1). উত্তর সব dp[i]-এর সর্বোচ্চ — কারণ LIS যেকোনো জায়গায় শেষ হতে পারে।

i      :  0  1  2  3  4  5  6  7
a[i]   :  3  1  4  1  5  9  2  6
dp[i]  :  1  1  2  1  3  4  2  4      max = 4
from j :  -  -  0  -  2  4  1  4      (one best j for each i; dp[7] = dp[4] + 1)

কেন ঠিক. a[i]-তে শেষ হওয়া যেকোনো বাড়তি subsequence-এর শেষের আগের উপাদানটি কোনো a[j], j < i, a[j] < a[i]; সেটি বাদ দিলে a[j]-তে শেষ হওয়া একটি বাড়তি subsequence থাকে, যার দৈর্ঘ্য ≤ dp[j] (induction). উল্টো দিকে dp[j]-এর ধারার শেষে a[i] জোড়া যায়। তাই সূত্রটি ঠিক। খরচ. প্রতিটি i-এর জন্য আগের সব j দেখা — মোট n(n − 1)/2 তুলনা, Θ(n²) সময়, Θ(n) জায়গা। “from j” কলাম (parent) রাখলে শেষ থেকে পেছনে হেঁটে subsequence পাওয়া যায়: 7 → 4 → 2 → 0 — মান 3 4 5 6. n = 5000-এ ১.২৫ কোটি তুলনা — ঠিক আছে; n = 2·10⁵-এ ২০০০ কোটি — অনেক বেশি। দরকার আরও চতুর state.

৮ · LIS O(n log n)-এ — patience sorting, tails আর binary search

স্তূপগুলোর ওপরের তাসগুলোকে একটি অ্যারেতে রাখুন — tails. এর অর্থ:

ছোট শেষ উপাদান ভালো, কারণ তাতে পরে বেশি সংখ্যা জোড়া যায়। নতুন সংখ্যা x এলে: tails-এ প্রথম যে ঘরের মান ≥ x, সেটি খুঁজুন (lower_bound, পর্ব ১৮-এর binary search). এমন ঘর না থাকলে x সবার চেয়ে বড় — tails-এর শেষে জুড়ুন (LIS এক বাড়ল)। থাকলে সেই ঘরে x বসান (সেই দৈর্ঘ্যের একটি আরও ভালো, ছোট শেষ পাওয়া গেল)। subsequence ফেরত পেতে প্রতিটি tails ঘরের পাশে সেই উপাদানের index (tailIdx) রাখুন, আর x বসানোর সময় parent[x-এর index] = বাঁ পাশের ঘরের index:

কেন ঠিক — invariant. দুটি কথা প্রতিটি ধাপের পর সত্য: (১) tails[k] সত্যিই দৈর্ঘ্য k + 1-এর বাড়তি subsequence-গুলোর সবচেয়ে ছোট শেষ; (২) tails কঠোরভাবে বাড়তি। (২) আসে (১) থেকে: দৈর্ঘ্য k + 2-এর একটি ধারা থেকে শেষ উপাদান বাদ দিলে দৈর্ঘ্য k + 1-এর একটি ধারা পাই, যার শেষ তার চেয়ে কঠোরভাবে ছোট, তাই tails[k] < tails[k + 1]. সাজানো বলেই binary search চলে। এখন x এলো, p = lower_bound. তখন tails[p − 1] < x, তাই দৈর্ঘ্য p-এর সেরা ধারার শেষে x জুড়ে দৈর্ঘ্য p + 1-এর একটি ধারা পাওয়া যায় যার শেষ x ≤ tails[p] — নতুন সবচেয়ে ছোট শেষ। k < p-এর ঘরগুলোতে x কোনো উন্নতি আনে না (সেগুলো আগেই x-এর চেয়ে ছোট), আর x দিয়ে দৈর্ঘ্য p + 2 বা বেশির ধারা শেষ করা যায় না, কারণ তার জন্য দৈর্ঘ্য p + 1-এর এমন ধারা লাগত যার শেষ < x, অথচ tails[p] ≥ x. তাই শুধু ঘর p বদলায়। ∎

খরচ. প্রতিটি উপাদানে একটি binary search — O(n log L), L = LIS-এর দৈর্ঘ্য, তাই O(n log n); জায়গা O(n). Michael Fredman ১৯৭৫ সালে দেখান, তুলনা-ভিত্তিক মডেলে এই হার মূলত সেরা। কঠোরভাবে নয়, শুধু “কমে না” (non-decreasing) ধারা চাইলে lower_bound-এর বদলে upper_bound (প্রথম > x) — সমান মান তখন ধারাকে লম্বা করে।

নিচের প্রোগ্রাম tails আর parent দিয়ে LIS বের করে, তারপর ৫০০টি এলোমেলো ছোট অ্যারেতে (০–১২ দৈর্ঘ্য, মান ০–৯, অনেক পুনরাবৃত্তিসহ) মিলিয়ে দেখে: দ্রুত পদ্ধতির দৈর্ঘ্য O(n²) DP-র সমান কি না, আর ফেরত আনা ধারাটি সত্যিই মূল অ্যারের একটি কঠোরভাবে বাড়তি subsequence কি না — ছোট আকারের stress testing.

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
pair<vector<int>, vector<int>> lisFast(const vector<int>& a) {     // O(n log n): patience sorting
    vector<int> tails, tailIdx, parent(a.size(), -1);
    for (int i = 0; i < (int)a.size(); ++i) {
        int p = lower_bound(tails.begin(), tails.end(), a[i]) - tails.begin();  // first tail >= a[i]
        if (p > 0) parent[i] = tailIdx[p - 1];
        if (p == (int)tails.size()) { tails.push_back(a[i]); tailIdx.push_back(i); }
        else { tails[p] = a[i]; tailIdx[p] = i; }
    }
    vector<int> seq;                                  // walk back through parent[]
    for (int i = tailIdx.empty() ? -1 : tailIdx.back(); i != -1; i = parent[i]) seq.push_back(a[i]);
    return {vector<int>(seq.rbegin(), seq.rend()), tails};
}
int lisSlow(const vector<int>& a) {                   // O(n^2): dp[i] = longest ending at i
    vector<int> dp(a.size(), 1);
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = 0; j < i; ++j) if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
    return a.empty() ? 0 : *max_element(dp.begin(), dp.end());
}
bool isIncSubseq(const vector<int>& s, const vector<int>& a) {     // strictly increasing subsequence of a?
    size_t k = 0;
    for (int x : a) if (k < s.size() && x == s[k]) ++k;
    return k == s.size() && is_sorted(s.begin(), s.end(), [](int x, int y) { return x <= y; });
}
int main() {
    vector<int> a{3, 1, 4, 1, 5, 9, 2, 6};
    auto [seq, tails] = lisFast(a);
    cout << "tails at the end:"; for (int x : tails) cout << ' ' << x;
    cout << "\nLIS length " << seq.size() << " :"; for (int x : seq) cout << ' ' << x;
    long long seed = 12345; int bad = 0;
    for (int t = 0; t < 500; ++t) {                   // small random arrays, fixed LCG seed
        vector<int> arr;
        for (int k = 0; k < t % 13; ++k) { seed = (seed * 1103515245 + 12345) % (1LL << 31); arr.push_back((int)(seed % 10)); }
        vector<int> s = lisFast(arr).first;
        bad += (int)s.size() != lisSlow(arr) || !isIncSubseq(s, arr);
    }
    cout << "\n500 random arrays checked, mismatches: " << bad << '\n';
}

tails at the end: 1 2 5 6
LIS length 4 : 1 4 5 6
500 random arrays checked, mismatches: 0

from bisect import bisect_left

def lis_fast(a):                                 # O(n log n): patience sorting
    tails, tail_idx, parent = [], [], [-1] * len(a)
    for i, x in enumerate(a):
        p = bisect_left(tails, x)                # first tail >= x (strictly increasing)
        if p > 0: parent[i] = tail_idx[p - 1]
        if p == len(tails): tails.append(x); tail_idx.append(i)
        else: tails[p] = x; tail_idx[p] = i
    seq, i = [], tail_idx[-1] if tail_idx else -1
    while i != -1: seq.append(a[i]); i = parent[i]
    return seq[::-1], tails

def lis_slow(a):                                 # O(n^2): dp[i] = longest ending at i
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]: dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

def is_inc_subseq(s, a):                         # strictly increasing and a subsequence of a?
    it = iter(a)
    return all(x < y for x, y in zip(s, s[1:])) and all(x in it for x in s)

a = [3, 1, 4, 1, 5, 9, 2, 6]
seq, tails = lis_fast(a)
print("tails at the end:", *tails)
print("LIS length", len(seq), ":", *seq)
seed, bad = 12345, 0
for t in range(500):                             # small random arrays, fixed LCG seed
    arr = []
    for _ in range(t % 13):
        seed = (seed * 1103515245 + 12345) % 2**31; arr.append(seed % 10)
    s, _ = lis_fast(arr)
    bad += len(s) != lis_slow(arr) or not is_inc_subseq(s, arr)
print("500 random arrays checked, mismatches:", bad)

tails at the end: 1 2 5 6
LIS length 4 : 1 4 5 6
500 random arrays checked, mismatches: 0

৯ · LIS-এর প্রয়োগ আর বিশাল W-এর knapsack

LIS-এর শক্তি হলো, অনেক সমস্যা একটু সাজিয়ে নিলেই LIS হয়ে যায়:

LIS-এর পরের ধাপ দুটি ক্রমের সবচেয়ে লম্বা সাধারণ subsequence (LCS) — পর্ব ৫৪-এর বিষয়। আরেকটি মজার সংযোগ: দুটি ক্রমের একটি যদি অন্যটির permutation হয় (সব উপাদান আলাদা), তাহলে LCS-কে LIS-এ নামিয়ে O(n log n)-এ করা যায়।

১০ · AI-এর যুগে DP — সঠিক দেখায়, এক লাইনে ভুল

Knapsack, coin change আর LIS ইন্টারনেটে লাখো বার লেখা হয়েছে, তাই AI এগুলোর কোড প্রায় সব সময় পরিচিত চেহারায় দেয়। কিন্তু এই পর্ব জুড়ে দেখেছেন, এই সমস্যাগুলোর আসল পার্থক্য প্রায়ই এক লাইনে — লুপের দিক, লুপের ক্রম, lower_bound না upper_bound. AI প্রায়ই দুটি কাছাকাছি সমস্যার সমাধান গুলিয়ে ফেলে, আর complexity লেখে “O(nW) — polynomial”.

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

• State-এর সংজ্ঞা বাংলায় এক বাক্যে লিখেছি, আর base case সেই সংজ্ঞা থেকেই এসেছে (যেমন ways[0] = 1)
• লুপের দিক মিলিয়েছি: প্রতিটি জিনিস একবার = উল্টো, যতবার খুশি = সামনে; উপায় গোনায় লুপের ক্রম প্রশ্নের সাথে মেলে
• ছোট এলোমেলো ইনপুটে DP-কে 2ⁿ-এর brute force-এর সাথে মিলিয়েছি
• Edge case: W = 0, খালি তালিকা, কোনো জিনিস একাই W-এর বড়, অঙ্ক বানানোই অসম্ভব, সব মান সমান
• n·W বা k·A-এর আকার দেখে সময় আর মেমরি হিসাব করেছি; বড় মানে long long বা mod
• উত্তরের সাথে তালিকা চাইলে reconstruction-ও যাচাই করেছি — ওজনের যোগফল ≤ W আর মানের যোগফল = উত্তর