ডায়নামিক প্রোগ্রামিং৭ মিনিট পড়া

মেমোইজেশন বনাম ট্যাবুলেশন (Memoization vs Tabulation)

টপ-ডাউন (Top-down) হলো এমন এক বন্ধুর কাছে কল করা যে আবার অন্য এক বন্ধুকে কল করে। আর বটম-আপ (Bottom-up) হলো সারি ধরে ধরে একটি স্প্রেডশিট পূরণ করার মতো ব্যাপার।
memoization:টপ-ডাউন (Top-down) · অলস (lazy) · \(O(states)\) টাইম বা সময়tabulation:বটম-আপ (Bottom-up) · ইগার বা আগ্রহী (eager) · \(O(states)\) টাইম বা সময়space winner:ট্যাবুলেশন (Tabulation) — সহজেই রোলিং-উইন্ডো (rolling-window) অপ্টিমাইজেশন প্রয়োগ করা যায়

একটি ডিপি বা DP সমস্যা (problem) চিনে ফেলার পর এবং আপনার স্টেট (state) ও রিকারেন্সকে (recurrence) সুস্পষ্টভাবে সংজ্ঞায়িত বা ডিফাইন (defined) করার পর, আপনি আরও একটি প্রশ্নের মুখোমুখি হয়ে থাকবেন: আমি আসলে কীভাবে এটিকে গণনায় আনবো বা কম্পিউট (compute) করবো? এটিকে করার প্রধানত দুটি পদ্ধতি বা অ্যাপ্রোচ (approaches) রয়েছে, এবং তারা ঠিক দুটি ভিন্ন ধরনের ব্যক্তিত্বের (personalities) মতো আচরণ করে।

মেমোইজেশন বা টপ-ডাউন (Memoization - top-down): সবচেয়ে বড় বা মূল সমস্যাটি থেকে শুরু করুন। এরপর ক্রমশ নিচের দিকে রিকার্স বা যান (Recurse down)। আপনি যদি আগে থেকেই কোনো সাব-প্রোব্লেম বা উপ-সমস্যার সমাধান করে থাকেন, তবে অবিলম্বে বা সাথে সাথেই শুধু সেই ক্যাশ (cached) করা উত্তরটি ফিরিয়ে দিন। আর যদি তা না হয়, তবে এটিকে আগে সমাধান করুন, তারপর ক্যাশে সংরক্ষণ (cache) করুন এবং সবশেষে সেটি ঘুরিয়ে ফেরত বা রিটার্ন (return) দিন। এটি অনেকটা কোনো বন্ধুকে কল করার মতো — যে কিনা তারপর হয়তো অন্য কোনো বন্ধুকে কল করতে পারে — যে হয়তো আবার অন্য কাউকে কল করতে পারে। আর এভাবেই ধীরে ধীরে এই চেইনটি বা শেকলটি একেবারের শেষ তলার তলানিতে গিয়ে পৌঁছায়, এবং তারপর সব উত্তরগুলো পুনরায় উপরের দিকে প্রচার (propagate) হতে থাকে।

ট্যাবুলেশন বা বটম-আপ (Tabulation - bottom-up): একেবারের সবচেয়ে ছোট সাব-প্রোব্লেমগুলো থেকে আপনার যাত্রা শুরু করুন। একটি টেবিল বা ছককে সবচেয়ে ছোট থেকে নিয়ে সবচেয়ে বড় পর্যন্ত মান দিয়ে পূরণ করুন, তবে এসময় খেয়াল রাখবেন যে প্রতিটি সেলের বা ঘরের নির্ভরতা বা ডিপেন্ডেন্সিগুলো (dependencies) যেন ইতিমধ্যেই আগে থেকে পূরণ করা থাকে। এটি ঠিক একটি স্প্রেডশিট (spreadsheet) পূরণ করার মতো ব্যাপার: যেখানে প্রতিটি ঘর বা সেল (cell) মূলত তার বাম দিকে বা উপরের দিকে থাকা ইতিমধ্যে গণা হয়ে যাওয়া বা কম্পিউট করা সেলগুলোকে (already-computed cells) ব্যবহার করে। এখানে কোনো রিকার্সন (recursion) নেই, কিংবা কোনো কল স্ট্যাকও (call stack) থাকে না।

দুটি অ্যাপ্রোচই (approaches) আপনাকে ঠিক একই ধরনের অ্যাসিম্পটোটিক সময় এবং স্পেস (same asymptotic time and space) প্রদান করবে। এখানকার পছন্দটি বা চয়েসটি মূলত সম্পূর্ণ নির্ভর করে বাস্তব নানা ধরনের ট্রেডঅফ (practical tradeoffs) বা সুবিধা-অসুবিধার ওপর।

মেমোইজেশন বা টপ-ডাউন — একটু আলসে পদ্ধতি (Memoization — The Lazy Approach)

রিকারেন্স বা পুনরাবৃত্তির ঠিক যেমনটা নির্দেশ করেছে, রিকার্সিভ সলিউশনটি বা রিকার্সিভ সমাধানটিও ঠিক সেভাবেই লিখুন, আর তারপর একেবারে এর উপরের অংশে একটি ক্যাশ চেকের (cache check) ব্যবস্থা করে দিন।

সুবিধাসমূহ (Advantages):
• এটি লেখা অনেক বেশি স্বাভাবিক বা ন্যাচারাল (Natural) হয়ে থাকে — এখানকার কোডটি সরাসরি এর রিকারেন্সকেই প্রতিফলিত (mirrors) করে থাকে।
• লেজি (Lazy) বা অলস: এটি কেবল সেই সমস্ত সাব-প্রোব্লেমগুলোকেই কম্পিউট (computes) বা গণনা করে, যেগুলো আসলে তার দরকার হয়। যদি আপনার সলিউশন্টি (solution) মূলত স্টেট স্পেসের (state space) কেবল একটি ছোট অংশকে স্পর্শ করে বা টাচ করে থাকে, তবে মেমোইজেশন ট্যাবুলেশনের (tabulation) ওই বাড়তি অপ্রয়োজনীয় কাজগুলো (wasted work) করা থেকে আপনাকে বাঁচাবে।
• পাইথনের (Python) @lru_cache, জাভাস্ক্রিপ্টের বা JavaScript-এর ক্লোজারস (closures), অথবা একটি ডিকশনারি (dictionary) দিয়ে একে বেশ সহজেই ইমপ্লিমেন্ট (implement) বা প্রয়োগ করে নেওয়া যায়।

অসুবিধাসমূহ (Disadvantages):
• ফাংশন কল ওভারহেড (Function call overhead) এবং কল স্ট্যাক মেমোরির (call-stack memory) প্রয়োজন হয়।
• স্ট্যাক ওভারফ্লোর রিস্ক বা ঝুঁকি (Stack overflow risk): যদি n=1,000,000 হয় এবং প্রতিটি রিকার্সিভ কল (recursive call) একটি করে নতুন ফ্রেম (frame) যোগ করতে থাকে, তবে বেশিরভাগ সিস্টেমের ডিফল্ট বা পূর্ব-নির্ধারিত কল স্ট্যাক (সাধারণত ১,০০০-১০,০০০ ফ্রেমস হয়ে থাকে) পুরোপুরি উপচে বা ওভারফ্লো (overflow) করে ফেলবে।
• স্পেস অপ্টিমাইজেশন (Space optimization) বা রোলিং অ্যারেস (rolling arrays) প্রয়োগ করা এতে বেশ কঠিন — কারণ এর রিকার্সিভ স্ট্রাকচার বা কাঠামোগত কারণে আপনি ঠিক কোন ক্যাশ করা স্টেটগুলোকে বা মানগুলোকে ফেলে বা বাদ দিতে (discard) পারবেন, তা নির্ধারণ করা খুব স্পষ্ট (non-obvious) হয়ে থাকে না।

ট্যাবুলেশন বা বটম-আপ — একটি খুব আগ্রহী বা ইগার পদ্ধতি (Tabulation — The Eager Approach)

পূরণ করার সঠিক ক্রম বা ফিল অর্ডার (fill order) (সাধারণত ছোট থেকে শুরু করে সবচেয়ে বড় ইনডেক্স বা সূচক পর্যন্ত) নির্ধারণ করুন, তারপর ইটারেট (iterate) করুন এবং প্রতিটি ঘর বা সেলকে (cell) পূরণ করতে থাকুন।

সুবিধাসমূহ (Advantages):
• কোনো স্পেশাল রিকার্সন ওভারহেড (recursion overhead) থাকে না, বা কোনো স্ট্যাক ওভারফ্লোরও (stack overflow) ভয় থাকে না।
• এর ফিল অর্ডার বা পূরণের ক্রমটি (Fill order) বেশ এক্সপ্লিসিট বা স্পষ্ট — আপনি চাইলেই পুরনো সারিগুলোকে বা রোলিং উইন্ডোগুলোকে (rolling window) বাদ দিয়ে মূলত \(O(n^2)\) থেকে \(O(n)\) তে বা \(O(n)\) থেকে \(O(1)\) তে স্পেস অপ্টিমাইজ (optimize space) করে নিতে পারেন।
• বাস্তবে এটি বেশ ভালো একটি বেটার ক্যাশ লোক্যালিটি (Better cache locality) প্রদান করে — এখানকার সিকোয়েনশিয়াল অ্যারে অ্যাক্সেস (sequential array access) অপেক্ষাকৃত দ্রুত কাজ করে।

অসুবিধাসমূহ (Disadvantages):
• 2D অথবা অনিয়মিত কোনো ডিপি-র (irregular DP) ক্ষেত্রে সঠিক ফিল অর্ডার বা পূরণের ক্রম নির্ধারণ করাটি বেশ অস্পষ্ট বা কঠিন (non-obvious) হতে পারে।
• এটি সমস্ত (all) সাব-প্রোব্লেম বা উপ-সমস্যাগুলোকেই কম্পিউট বা গণনা করে রাখে, এমনকি ফাইনাল উত্তরের জন্য যেগুলির কোনও প্রয়োজনই (not needed for the final answer) নেই সেগুলোকেও।

স্পেস অপ্টিমাইজেশন — ট্যাবুলেশনের সুপারপাওয়ার বা অসীম ক্ষমতা (Space Optimization — Tabulation's Superpower)

বেশিরভাগ ডিপি রিকারেন্সই (DP recurrences) মূলত কেবল এক বা দুটি সারির (rows) দিকেই ফিরে তাকায়। যখন ঠিক এমনটাই ঘটে বা রিকোয়ারমেন্ট থাকে, তখন আপনি চাইলে সহজেই আপনার পুরনো সারির (rows) ডেটাগুলোকে ফেলে দিয়ে শুধুমাত্র আপনার জন্য প্রয়োজনীয় টুকুকেই জমিয়ে রাখতে পারবেন।

ফিবোনাচি (Fibonacci): dp[i] = dp[i-1] + dp[i-2]। এখানে শুধুমাত্র সর্বশেষ দুটো (last two) মানেরই প্রয়োজন। পরিমাণ বা স্পেস (Space): \(O(n)\) → \(O(1)\)।

0/1 ন্যাপস্যাক (0/1 Knapsack): dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val)। এক্ষেত্রে শুধু আপনার পূর্ববর্তী সারিরই (previous row) প্রয়োজন। স্পেস (Space): \(O(n \cdot W)\) → \(O(W)\)। (আপনার প্রয়োজনীয় ডেটা বা ভ্যালুর যেন কোনো ক্ষতি (overwriting) না হয়, এজন্য w-কে উল্টোদিকে বা রিভার্স (reverse) ডিরেকশনে ইটারেট (Iterate) করতে পারেন।)

অপ্টিমাইজেশনের (optimization) এই কাজগুলো মূলত ট্যাবুলেশনের (tabulation) মাধ্যমে করা অত্যন্ত সোজাসাপ্টা ও সহজ (straightforward) একটি ব্যাপার। পক্ষান্তরে, মেমোইজেশনের (memoization) সাহায্যে এটি করার জন্য আপনাকে ঠিক কোন কোন ক্যাশড স্টেটগুলো (cached states) দরকারি তা নিজের হাতে ট্র্যাক (track) করতে হবে — যা তুলনামূলক অনেক বেশি দুঃসাধ্য ও কঠিন (much harder) একটা কাজ।

দ্রষ্টব্য: রুল অফ থাম্ব (Rule of thumb): যখন স্টেট স্পেসের (state space) সাইজ অনেক বড় হয়, কিন্তু তার মধ্য থেকে শুধুমাত্র সামান্য একটি ভগ্নাংশই বা ফ্র্যাকশনই (fraction) আপনার শুরুর বিন্দু থেকে পৌঁছানোর যোগ্য (reachable) হয়, তখন মেমোইজেশন (memoization) ব্যবহার করুন। আর যখন আপনার স্পেস অপ্টিমাইজেশন (space optimization) বা স্ট্যাকের গভীরতা (stack depth) সংক্রান্ত চিন্তার প্রয়োজন থাকে, তখন নির্দ্বিধায় ট্যাবুলেশন (tabulation) ব্যবহার করুন। তবে যদি আপনার কোনো কনফিউশন (doubt) থেকে থাকে, সেক্ষেত্রে ট্যাবুলেশনকে (tabulation) ব্যবহার করাই মূলত সবচেয়ে নিরাপদ বা সেফার (safer) পছন্দ মানা হয়।
Click chart to zoom
সিদ্ধান্ত নেওয়ার ফ্লোচার্ট বা ডায়াগ্রাম: মেমোইজেশন (নীল) এবং ট্যাবুলেশন (সবুজ) এর মাঝে সঠিকটি বেছে নেওয়া

মেমোইজেশন বনাম ট্যাবুলেশন — ফিবোনাচি এবং 0/1 ন্যাপস্যাক

from functools import lru_cache


# === FIBONACCI ===
# Top-down memoization
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)


# Bottom-up tabulation (space optimised to O(1))
def fib_tab(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a+b
    return b


print(f"Fib(10) memo: {fib_memo(10)}, tab: {fib_tab(10)}")


# === 0/1 KNAPSACK ===
# Top-down memoization
def knapsack_memo(weights, values, capacity):
    @lru_cache(maxsize=None)
    def dp(i, w):
        if i == 0 or w == 0: return 0
        if weights[i-1] > w:
            return dp(i-1, w)
        return max(dp(i-1, w), dp(i-1, w-weights[i-1]) + values[i-1])
    return dp(len(weights), capacity)


# Bottom-up tabulation (space optimised: single row O(W))
def knapsack_tab(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w-1, -1):  # reverse to avoid overwrite
            dp[c] = max(dp[c], dp[c-w] + v)
    return dp[capacity]


wt = [2, 3, 4, 5]
val = [3, 4, 5, 6]
cap = 8
print(f"Knapsack memo: {knapsack_memo(wt, val, cap)}")
print(f"Knapsack tab:  {knapsack_tab(wt, val, cap)}")
Output
Fib(10) memo: 55, tab: 55
Knapsack memo: 10
Knapsack tab:  10

Complexity

⏱️ মেমোইজেশন টাইম (Memoization time)
ক্যাশ হিট (Cache hit) হলে এটি তাৎক্ষণিকভাবেই (instantly) রিটার্ন বা ফিরে আসে; মানে এখানকার সর্বমোট কাজ = ভিন্ন ভিন্ন স্টেটের (states) সংখ্যা × ট্রানজিশনের খরচ (transition cost)
প্রতিটি স্টেট (state) শুধুমাত্র একবার গণনা (computed) করা হয় \(O(states)\)
📚 মেমোইজেশন স্পেস (Memoization space)
রিকার্সনের গভীরতা বা ডেপথ মূলত \(O(n)\) স্ট্যাক ফ্রেম (stack frames) যোগ করতে থাকে — যার কারণে বড় n এর জন্য স্ট্যাক ওভারফ্লোর (stack overflow) ঝুঁকি থেকে যায়
ক্যাশ (Cache) + কল স্ট্যাক (call stack) \(O(states + depth)\)
⏱️ ট্যাবুলেশন টাইম (Tabulation time)
এর অ্যাসিম্পটোটিক টাইমও (asymptotic time) মূলত সেম বা একই থাকে; তবে বাস্তবিক ক্ষেত্রে (practice) কোনো প্রকার ফাংশন কল ওভারহেড (function call overhead) না থাকার কারণে এটি কিছুটা দ্রুত কাজ করে
পুরো সম্পূর্ণ টেবিলটিই (entire table) ফিল বা পূরণ করা হয় \(O(states)\)
📦 ট্যাবুলেশন স্পেস (সস্পূর্ণ বা ফুল টেবিল / full table)
গণনা বা কম্পিউট (computed) করা প্রতিটি মানকেই (value) স্টোর করে রাখা হয় — পরবর্তীতে যদি ঐসব মানগুলোর দরকার পড়ে, তখন এই ব্যবস্থাটি প্রয়োজনীয় হয়ে ওঠে
সমস্ত স্টেট বা মানগুলোকেই সঞ্চয় (stored) করে রাখা হয় \(O(states)\)
✂️ ট্যাবুলেশন স্পেস (রোলিং উইন্ডো / rolling window)
যখন এর রিকারেন্স (recurrence) মাত্র নির্দিষ্ট সংখ্যক সারি পিছনের দিকে নজর রাখে — তখন শুধু সেগুলোকে রেখেই বাকি সমস্ত ডেটা নির্দ্বিধায় ফেলে দেওয়া (discard) যায়
পূর্ববর্তী সারিতে(গুলোতে) শুধুমাত্র (Previous row(s) only) \(O(1)\) থেকে \(O(row \ space)\)

ছোট কুইজ

একটি লিনিয়ার বা রৈখিক রিকারেন্স (linear recurrence) ব্যবহার করে আপনাকে dp[1,000,000]-কে গণনা বা কম্পিউট (compute) করার নির্দেশ দেওয়া হলে, নিচের কোনটি বেশি নিরাপদ (safer) বা ভালো পদ্ধতি, এবং কেন?

পড়া চালিয়ে যান

ডিপি প্যাটার্ন (DP Pattern)
একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
→
1D ডিপি (1D DP)
সিঁড়ি বেয়ে ওপরে ওঠার মতোই — ধাপে ধাপে নিজের উত্তর তৈরি বা নির্মাণ করুন
→
0/1 ন্যাপস্যাক (0/1 Knapsack)
সর্বোচ্চ মূল্যের (value) জন্য একটি ব্যাগ বা স্যুটকেস প্যাক করুন — যেখানে প্রতিটি জিনিস বা আইটেম হয় পুরোপুরি নিতে হবে নতুবা একদমই নেওয়া যাবে না (all-or-nothing)
→