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

ডিপি প্যাটার্ন (DP Pattern)

একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
requires:ওভারল্যাপিং সাব-প্রোব্লেম (Overlapping subproblems) + অপ্টিমাল সাবস্ট্রাকচার (optimal substructure)approach:স্টেট (State) → ট্রানজিশন (Transition) → বেস কেস (Base case)vs naive:এক্সপোনেনশিয়াল (Exponential) → পলিনোমিয়াল (Polynomial)

ধরুন আপনি একটি বিশাল বড় জিগস পাজল (jigsaw puzzle) জোড়া লাগাচ্ছেন আর আপনি বারবার একই কোণার অংশটি সমাধান করছেন — যতবারই আপনি সেটিতে ফিরে আসছেন ততবারই। ঠিক এর কাজটাই মূলত সাধারণ রিকার্সন (naive recursion) করে থাকে। ডায়নামিক প্রোগ্রামিং (Dynamic Programming) বা (DP) বলে যে: প্রতিটি টুকরোকে একবারই সমাধান করুন, ফলাফলটিকে একটি স্টিকি নোটে বা কাগজে লিখে রাখুন এবং পরবর্তীতে আপনার যদি এটিকে আবার কখনো প্রয়োজন হয় তবে সেখান থেকেই শুধু দেখে নিন।

এই চমৎকার সরল ধারণাটি — শুধু ফলাফল ক্যাশ (cache) বা জমা করে রাখুন, কখনোই পুনরায় কম্পিউট (recompute) বা গণনা করবেন না — মূলত এক্সপোনেনশিয়াল অ্যালগরিদমগুলোকে (exponential algorithms) পলিনোমিয়াল বা বহুপদী (polynomial) অ্যালগরিদমে পরিণত করে বা বদলে দেয়।

এর জন্য প্রয়োজনীয় দুটি বৈশিষ্ট্য (Two Properties You Need)

ওভারল্যাপিং সাব-প্রোব্লেম বা উপ-সমস্যা (Overlapping Subproblems): এখানে রিকার্সিভ সমাধানটি (recursive solution) মূলত একই সাব-প্রোব্লেম বা উপ-সমস্যাগুলোকেই বারবার কল (calls) করে থাকে। এর ক্লাসিক একটি উদাহরণ হলো: ফিবোনাচি নম্বর বা সংখ্যা (Fibonacci numbers)। F(5) গণনা করার জন্য মূলত F(4) এবং F(3)-কে কল করা হয়। আর আবার F(4) মূলত F(3) এবং F(2)-কে কল করে থাকে। এর ফলে F(3) দুবার এবং F(2) তিনবার গণনা করা হয়... কোনো স্টোর বা ক্যাশিং (caching) ছাড়া, শুধু F(50) কে গণনা করতেই প্রায় ১ ট্রিলিয়নের (trillion) বা এক লক্ষ কোটিরও বেশি ফাংশন কল করতে হয়। কিন্তু এর সাথে ক্যাশ (caching) যুক্ত করলে: শুধুমাত্র 50 টি স্বতন্ত্র বা ইউনিক (unique) কল করা লাগে, এবং কাজ শেষ।

অপ্টিমাল সাবস্ট্রাকচার (Optimal Substructure): যেকোনো বড় সমস্যার অপ্টিমাল বা সর্বোত্তম সমাধান মূলত তার ছোট সাব-প্রোব্লেম বা উপ-সমস্যার অপ্টিমাল বা সর্বোত্তম সমাধানের ওপর নির্ভর করেই তৈরি হয়ে থাকে। ধরি B-এর মাধ্যমে A থেকে C-তে যাওয়ার সবচেয়ে ছোট রুট বা শর্টেস্ট পাথ (Shortest path) বের করতে হবে: সেক্ষেত্রে A→B অংশটিকে অবশ্যই A→B-এর জন্য সবচেয়ে ছোট পাথ হতে হবে এবং B→C অংশটি কেউ অবশ্যই B→C-এর সবচেয়ে ছোট পাথ হতে হবে। যদি এর কোনো সাব-পাথ (sub-path) বা উপ-পথ সাব-অপ্টিমাল (suboptimal) বা অপরদর্শী বা সর্বোত্তম না হতো, তবে আপনি চাইলে সেটির উন্নতি ঘটিয়ে নিজের জন্য আরও ভালো একটি সামগ্রিক পাথ বা পথ পেতে পারতেন — যাকে বিপরীত বক্তব্য বা কনট্রাডিকশন (contradiction) বলা হয়। তাই এখানে অপ্টিমাল সাবস্ট্রাকচার বা বৈশিষ্ট্যটি টিকে থাকে বা কাজ করে।

উভয় বৈশিষ্ট্যই একত্রে যার অর্থ দাঁড়ায়: প্রতিটি সাব-প্রোব্লেমকে বা উপ-সমস্যাকে সর্বোত্তম উপায়ে (optimal fashion) ঠিক একবারই কম্পিউট (compute) বা গণনা করুন, তারপর জিনিসগুলোকে একত্রিত করুন এবং আপনার কাজ শেষ হয়ে যাবে।

ডিপি (DP) ডিজাইনের ফ্রেমওয়ার্ক (The DP Design Framework)

১. স্টেট ডিফাইন (Define the state) বা অবস্থা সংজ্ঞায়িত করুন: এখানে মূলত dp[i] (অথবা dp[i][j]) দিয়ে কী বোঝানো হয়েছে? সেটিকে খুব নিখুঁতভাবে বা প্রিসাইজলি (precise) লিখুন এবং প্রকাশ করুন। ভুল স্টেট (state) ডিফাইন বা সংজ্ঞায়িত করার মানে হলো → এর ডাউনস্ট্রিমে (downstream) থাকা সবকিছুই ভুল হবে।

২. রিকারেন্স বা ট্রানজিশনটি লিখুন (Write the recurrence / transition): dp[i]-কে ছোট ইনডেক্স বা সূচকের (indices) মাধ্যম ব্যবহার করে প্রকাশ করুন। এটি এখানকার সবচেয়ে কঠিন এবং সৃজনশীল (creative) একটি ধাপ বা স্টেপ।
• ফিবোনাচি (Fibonacci): dp[i] = dp[i-1] + dp[i-2]
• 0/1 ন্যাপস্যাক (Knapsack): dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
• LCS বা লনজেস্ট কমন সাবসিকোয়েন্স: s1[i]==s2[j] হলে dp[i][j] = dp[i-1][j-1]+1 নতুবা max(dp[i-1][j], dp[i][j-1])

৩. বেস কেসগুলো সংজ্ঞায়িত বা ডিফাইন করুন (Define base cases): এগুলো হলো সবচেয়ে ছোট সাব-প্রোব্লেম বা উপ-সমস্যা, আপনি যেগুলোর উত্তর সরাসরি দিতে পারেন।
• ফিবোনাচি (Fibonacci): dp[0]=0, dp[1]=1
• ন্যাপস্যাক (Knapsack): সমস্ত w-এর জন্য dp[0][w]=0 (কোনো আইটেম নেই → তাই কোনো ভ্যালু (value) বা মান নেই)

৪. অর্ডার পূরণ করা (Fill order / Tabulation) বা মেমোইজ (Memoize) করা: হয় আপনি টেবিলটিকে বটম-আপ বা নিচ-থেকে-উপর পদ্ধতিতে (ট্যাবুলেশন / tabulation) পূরণ করতে পারেন, যেখানে প্রয়োজন হওয়ার আগেই সমস্ত ডিপেন্ডেন্সিগুলো (dependencies) কম্পিউট বা গণনা করা হয়, অথবা টপ-ডাউন বা উপর-থেকে-নিচ রিকার্সনে (memoization / মেমোইজেশন) গিয়ে সরাসরি একটি ক্যাশ বা মেমরিকে (cache) যোগ করে নিতে পারেন।

Click chart to zoom
চার ধাপের ডিপি ডিজাইন পাইপলাইন বা ফ্রেমওয়ার্ক: স্টেট (state) বা অবস্থা সংজ্ঞায়িত করুন, রিকারেন্স (recurrence) লিখুন, বেস কেসগুলো (base cases) সেট করুন, তারপর মেমোইজেশন (memoization) বা ট্যাবুলেশন (tabulation) বেছে নিন — এবং যদি সম্ভব হয় তাহলে স্পেস বা মেমরি (space) অপ্টিমাইজ করুন বা সেভ করুন।

ডিপি (DP) বনাম গ্রিডি (Greedy) বনাম ডিভাইড অ্যান্ড কঙ্কার (Divide & Conquer)

এই তিনটি পদ্ধতিই সমস্যাগুলোকে ছোট টুকরোতে ভেঙে ফেলে, কিন্তু প্রত্যেকে তা আলাদাভাবে করে থাকে:
• ডিভাইড অ্যান্ড কঙ্কার (Divide & Conquer): সাব-প্রোব্লেমগুলো একে অপরের থেকে সম্পূর্ণ স্বাধীন (independent) থাকে — প্রতিটিকে একবার সমাধান করে তারপর একত্রিত করে। (উদাহরণ: মার্জ সর্ট বা Merge sort, ক্লোজেস্ট পেয়ার বা closest pair)
• গ্রিডি (Greedy): একটি স্থানীয়ভাবে সর্বোত্তম (locally-optimal) বা বুদ্ধিদীপ্ত পছন্দ করে, কখনোই পেছনে ফিরে তাকায় না। এটি কেবল তখনই কাজ করে যখন গ্রিডি-চয়েস (greedy-choice) বা বুদ্ধিদীপ্ত পছন্দের বৈশিষ্ট্যটি বজায় থাকে বা কাজ করে।
• ডিপি (DP): সাব-প্রোব্লেমগুলো ওভারল্যাপ (overlap) করে, তাই ফলাফলগুলোকে ক্যাশে (cache) স্টোর করে রাখে। প্রতিটি ধাপে থাকা সমস্ত অপশনগুলোর বা চয়েসগুলো (choices) বিবেচনা করে। গ্রিডি (greedy) পদ্ধতির তুলনায় এটি দশগুণ বেশি পাওয়ারফুল বা শক্তিশালী হলেও, এটি সাধারণত বেশ ধীরগতির (slower) হয়ে থাকে।

একটি সহজ নিয়ম বা রুল অফ থাম্ব (Rule of thumb) হলো: যেকোনো সমস্যায় প্রথমেই গ্রিডি (greedy) পদ্ধতি ট্রাই (try) বা চেষ্টা করে দেখা। তবে গ্রিডি বা বুদ্ধিদীপ্ত চয়েসের (greedy choice) ক্ষেত্রে যদি আপনি এর বিপরীতে কোনো কাউন্টার-অ্যাক্সাম্পল (counterexample) বা উত্তর খুঁজতে বা প্রমাণ করতে ব্যর্থ হন, তাহলে আপনার উচিত সরাসরি ডিপি-তে (DP) সুইচ করা বা বদলানো।

Click chart to zoom
সিদ্ধান্তের বা ডিসিশনের ফ্লোচার্ট (Decision flowchart): ছোট সাব-প্রোব্লেম বা উপ-সমস্যাগুলো দিয়ে তৈরি একটি সমস্যার ক্ষেত্রে, আপনার কি ডিভাইড অ্যান্ড কঙ্কার (Divide & Conquer), গ্রিডি (Greedy), নাকি ডিপি (DP) ব্যবহার করা উচিত তা এই ফ্লোচার্টটির মাধ্যমে নির্ধারণ করুন।
দ্রষ্টব্য: অদ্বিতীয় বা ইউনিক সাব-প্রোব্লেমের (distinct subproblems) সংখ্যাটিই হলো এখানকার মূল বিষয় বা কি নম্বর (key number)। যদি সেখানে শুধু n-সংখ্যক স্বতন্ত্র সাব-প্রোব্লেম বা ইউনিক উপসমস্যা (যেমন: ফিবোনাচি 0..n) থাকে এবং তাদের ডিপেন্ডেন্সিগুলো (dependencies) জানার পর প্রতিটিকে সমাধান করতে \(O(1)\) পরিমাণ সময় লাগে, তবে কোনো সাধারণ রিকার্সন (naive recursion) সেগুলোকে যত পরিমাণ সংখ্যক বারই বা যতোবারই পুনরায় গণনা করুক না কেন বা পুনর্গণনা করুক না কেন — আপনার ডিপি (DP) কিন্তু ঠিকই \(O(n)\) সময়েই সফলভাবে এর রান বা সমাধান করতে পারবে।

ডিপি ফ্রেমওয়ার্ক (DP Framework) — ফিবোনাচি (ফ্ল্যাট/Naive → মেমোইজ/Memo → টেবিল/Tab → স্পেস-সাশ্রয়ী/Space-Optimised)

import sys
from functools import lru_cache


# 1. Naive — exponential O(2^n)
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)


# 2. Memoization / top-down — O(n)
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)


# 3. Tabulation / bottom-up — O(n) time, O(n) space
def fib_tab(n):
    if n <= 1: return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]


# 4. Space-optimised — O(n) time, O(1) space
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b
    return a


for fn, name in [(fib_memo,'memo'),(fib_tab,'tab'),(fib_opt,'opt')]:
    print(f"fib(10) [{name}] = {fn(10)}")
Output
fib(10) [memo] = 55
fib(10) [tab] = 55
fib(10) [opt] = 55

Complexity

🐢 লেইজি বা ফ্ল্যাট ফিবোনাচি (Naive Fibonacci) (ক্যাশ ছাড়া)
প্রতিটি কল আরও নতুন দুটি কল তৈরি করে বা স্পন (spawns) করে; একই সাব-প্রোব্লেম বা উপসমস্যা অসংখ্য বা এক্সপোনেনশিয়াল (exponentially) সংখ্যক বার পুনর্গণনা করা হয়
এক্সপোনেনশিয়াল ব্লোআপ (Exponential blowup) \(O(2^n)\)
⚡ মেমোইজেশন সহ ফিবোনাচি (Fibonacci with memoization)
এখানে n সংখ্যক অনন্য স্টেট (F(0)..F(n)) থাকে; প্রতিটিকে একবার কম্পিউট (compute) বা গণনা করে সেগুলোকে ক্যাশ (cache) বা জমা করা হয়
প্রতিটি স্টেট (state) বা অবস্থা মূলত একবার গণনা করা হয় \(O(n)\)
📏 সাধারণ বা জেনারেল 1D ডিপি (General 1D DP)
n সংখ্যক স্টেট বা অবস্থা, প্রতিটির জন্য ট্রানজিশন বা পরিবর্তন \(O(1)\) = সর্বমোট \(O(n)\)
স্টেট কাউন্টের বা অবস্থার গণনানুসারে লিনিয়ার (Linear in state count) \(O(n)\)
📐 সাধারণ বা জেনারেল 2D ডিপি (General 2D DP)
n × m সংখ্যক স্টেট গ্রিড, প্রতিটির জন্য ট্রানজিশন বা পরিবর্তন \(O(1)\) — যার মধ্যে রয়েছে LCS, এডিট ডিসট্যান্স (edit distance), ইত্যাদি
কোয়াড্র্যাটিক বা দ্বিঘাত (Quadratic) \(O(n \cdot m)\)
📦 মেমরি বা স্পেস (রোলিং অ্যারে ট্রিক / rolling array trick)
যেখন এর রিকারেন্স (recurrence) শুধুমাত্র কিছু ফিক্সড বা নির্দিষ্ট সংখ্যার সারি বা রো (row)-এর দিকে ফেরত তাকায়, তখন পুরনো সারিগুলোকে সহজেই বাতিল বা বাদ দেওয়া যেতে পারে বা ডেসকার্ড (discard) করা যায়
কমানো বা সংক্ষিপ্ত সাইজ টেবিল (Reduced table) \(O(1)\) থেকে \(O(\text{row size})\)

ছোট কুইজ

সাধারণ বা নেইভ (Naive) ফিবোনাচির (Fibonacci) সময় জটিলতা হলো \(O(2^n)\)। তবে সেটিকে কমিয়ে \(O(n)\)-এ রূপান্তরিত করতে ডিপি (DP) মূলত কোন জিনিসটির সুবিধা ব্যবহার করে থাকে?

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

মেমোইজেশন বনাম ট্যাবুলেশন (Memoization vs Tabulation)
টপ-ডাউন (Top-down) হলো এমন এক বন্ধুর কাছে কল করা যে আবার অন্য এক বন্ধুকে কল করে। আর বটম-আপ (Bottom-up) হলো সারি ধরে ধরে একটি স্প্রেডশিট পূরণ করার মতো ব্যাপার।
→
গ্রিডি প্যাটার্ন বা লোভী পদ্ধতি (Greedy Pattern)
দাওয়াতের মাংসের সবচেয়ে বড় টুকরোটি সবসময় তুলে নিন — কখনো এটি সেরা সমাধান দেয়, আবার কখনো দেয় না
→
1D ডিপি (1D DP)
সিঁড়ি বেয়ে ওপরে ওঠার মতোই — ধাপে ধাপে নিজের উত্তর তৈরি বা নির্মাণ করুন
→