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

1D ডিপি (1D DP)

সিঁড়ি বেয়ে ওপরে ওঠার মতোই — ধাপে ধাপে নিজের উত্তর তৈরি বা নির্মাণ করুন
time:লিনিয়ার বা রৈখিক (Linear) · \(O(n)\)space:\(O(n)\) বা অপ্টিমাইজড (optimized) হিসেবে \(O(1)\)

ধরুন আপনি সিঁড়ি বেয়ে উপরে উঠছেন (climbing a staircase)। ১০ নম্বর ধাপে পৌঁছানোর জন্য, আপনাকে অবশ্যই ৯ নম্বর ধাপ (এক ধাপ উপরে) থেকে অথবা ৮ নম্বর ধাপ (দুই ধাপ উপরে) থেকে আসতে হতো। তাছাড়া অন্য কোনো উপায় নেই বা থাকার কথাও নয়। এই সাধারণ বা সিম্পল (simple) পর্যবেক্ষণটিই হলো 1D ডায়নামিক প্রোগ্রামিং (1D Dynamic Programming) এর মূল ভিত্তি বা কথা।

প্রতিবার শুরু (scratch) থেকে সম্ভাব্য প্রতিটি রুট বা পাথ (path) চেষ্টা ও পরীক্ষা করার পরিবর্তে, ডিপি (DP) মূলত বলে: "আমি ইতিমধ্যেই ৮ নম্বর এবং ৯ নম্বর ধাপে পৌঁছানোর সর্বোত্তম বা খুব ভালো উপায়গুলি বের করে ফেলেছি — তাই আমার জন্য ১০ নম্বর ধাপটি নিতান্তই সহজ বা ট্রিভিয়ালি ইজি (trivial) একটি ব্যাপার।" এভাবেই আমরা যা ইতোমধ্যে জানি সেটিকে ব্যবহার করে, টুকরো টুকরো বা একটু একটু করে নিজের কাঙ্খিত উত্তর তৈরি করি।

এর প্রবেশদ্বার বা গেটওয়ে (Gateway): ফিবোনাচি (Fibonacci)

ফিবোনাচি অনুক্রম বা সিকোয়েন্সটি (Fibonacci sequence) (০, ১, ১, ২, ৩, ৫, ৮, …) মূলত F(n) = F(n-1) + F(n-2) হিসেবে ডিফাইন বা সংজ্ঞায়িত করা থাকে। একটি সাধারণ রিকার্সিভ পদ্ধতিটি বা নেইভ রিকার্সন (naive recursive) পদ্ধতি মূলত F(5), F(6), F(7)… এর গভীরে থাকা F(3)-কে বারবার এক্সিকিউট বা পুনর্গণনা করতে থাকে আর ক্রমশ তা \(O(2^n)\) পরিমাণ বা বহুগুণ কাজে রূপান্তরিত হয়ে বিশাল এক অবস্থার সৃষ্টি করে বা স্নোবল (snowball) হয়ে যায়।

ডিপি-র (DP) ফিক্স বা সমাধানটি বেশ সোজা: F(0), F(1), F(2), … ক্রমানুসারে (order) হিসেব বা গণনা করুন এবং প্রতিটি ফলাফল সংরক্ষণ বা সেভ করে রাখুন। প্রতিটি মান পেতে বা ভ্যালুর জন্য মূলত একবার করে যোগ করতে হয়। যার সর্বমোট পরিমাণ বা টাইম: \(O(n)\)। এবং যদি আপনার শুধুমাত্র শেষের বা লাস্ট (last) দুটি মান বা ভ্যালুরই প্রয়োজন হয়, তবে আপনি সম্পূর্ন অ্যারেটির (array) বদলে মাত্র দুটি ভেরিয়েবল (variables) সংরক্ষণ করে রাখতে পারেন — যা হবে \(O(1)\) স্পেস (space)।

সিঁড়িতে আরোহণ করা (Climbing Stairs)

আপনি চাইলে একবারে ১ বা ২ ধাপ উঠতে পারেন। আপনি মোট কয়টি ভিন্ন উপায়ে n ধাপে বা স্টেপে পৌঁছাতে পারবেন? প্রতিটি i ধাপে, আপনি i-1 ধাপ বা i-2 ধাপ থেকে এসেছেন, তাই: dp[i] = dp[i-1] + dp[i-2]। এর বেস কেসগুলো (Base cases) হলো: dp[1] = 1, dp[2] = 2। এটি ঠিক ফিবোনাচির (Fibonacci) মতোই, শুধু মাত্র এটি এর থেকে এক ধাপ পিছিয়ে থাকে বা অফসেট (offset) করা থাকে।

হাউস রবার বা বাড়ি চুরি (House Robber)

ধরা যাক, একটি সারিতে কিছু বাড়ি রয়েছে আর এর প্রতিটির ভেতরে কিছু টাকা বা ডলার পরিমাণ রয়েছে, কিন্তু আপনি কোনোভাবেই পাশাপাশি থাকা দুটি বাড়িতে চুরি করতে পারবেন না। আপনাকে এর চুরির মোট লভ্যাংশ বা পরিমাণটিকে সর্বোচ্চ বা ম্যাক্সিমাইজ (maximize) করতে হবে। প্রতিটি i তম বাড়িতে আপনি একটি সুযোগ বা চয়েস পান: হয় এটিকে এড়িয়ে যান বা স্কিপ (skip) করুন (যা i-1 নম্বর বাড়ির মোট পরিমাণ বা হাল) অথবা সেটিতে চুরি করুন (দুটি বাড়ি আগে অর্থাৎ i-2 এ যে পরিমাণ টাকা ছিল, তার সাথে এই বাড়ির টাকা যোগ করুন)। রিকারেন্স (Recurrence) বা ফিরে আসা অ্যালগরিদমটি হলো: dp[i] = max(dp[i-1], dp[i-2] + nums[i])।

রোলিং-ভেরিয়েবল ট্রিক (The Rolling-Variable Trick)

যখনি dp[i] শুধু কিছু নির্দিষ্ট সংখ্যক (fixed number) ধাপ পেছনের দিকে (যেমন ধরুন সর্বশেষ ২ টির দিকে) নির্দেশ করে, তখন আপনার সম্পূর্ণ অ্যারেটির বা অ্যারের (array) কোনো প্রয়োজন নেই। শুধু ওই কয়েকটি বা ফিউ (few) ভেরিয়েবলকে (variables) সংরক্ষণ করুন, প্রতিটি ধাপে সেগুলোকে আপডেট করুন, এবং এর মাধ্যমে আপনার ব্যবহৃত স্পেস বা মেমরি স্থান \(O(n)\) থেকে সোজা \(O(1)\) এ নেমে আসবে। এই ট্রিকটি বা কৌশলটি ফিবোনাচি, ক্লাইম্বিং স্টায়ারস (climbing stairs), হাউস রবার (house robber) সহ আরও অনেক 1D ডিপি (DP) সমস্যার সমাধান করার জন্য চমৎকারভাবে কাজ করে।

দ্রষ্টব্য: ডিপি (DP) মূলত কোনো চতুর বা খুব দ্রুত শর্টকাট (clever shortcut) খুঁজে বের করে না — বরং এটি এক কাজ বারবার করা বা পুনরাবৃত্তি (repeating work) হওয়াকে এড়িয়ে চলে বা অ্যাভয়েড করে। প্রতিটি সাব-প্রোব্লেম বা উপ-সমস্যাকে ঠিক একবার (exactly once) সমাধান করা হয়, এবং তারপর সেটাকে মনে রাখা বা রিমেম্বার্ড (remembered) করা হয়। মূলত এভাবেই ডায়নামিক প্রোগ্রামিং (DP) কাজ করে থাকে।

হাউস রবার (House Robber) — রোলিং ভেরিয়েবলসহ (rolling variables) ডিপি

def rob(nums):
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1


print(rob([2, 7, 9, 3, 1]))   # 12
print(rob([1, 2, 3, 1]))      # 4
Output
12
4

Complexity

🐌 সাধারণ বা নেইভ ফিবোনাচি রিকার্সন (Naive Fibonacci recursion)
অসংখ্যবার একই সাব-প্রোব্লেম বা উপ-সমস্যা পুনঃগণনা (recomputed) করা হয় — বৃদ্ধি পেতে পেতে তা একটি বাইনারি ট্রি-র (binary tree) মতো আকার ধারণ করে
এক্সপোনেনশিয়াল (Exponential) \(O(2^n)\)
⚡ 1D ডিপি টাইম (1D DP time)
n সংখ্যক স্টেটগুলোর প্রতিটিকে ঠিক একবার বা এক্সাক্টলি ওয়ান্স (exactly once) গণনা করা হয়
লিনিয়ার (Linear) \(O(n)\)
📦 1D ডিপি স্পেস, সম্পূর্ণ অ্যারে (1D DP space, full array)
সমস্ত n সংখ্যক স্টেট সেভ বা স্টোর (store) করে রাখুন — এটি কাজে আসে যখন আপনার পুরো মূল পাথটি (original path) পুনরায় তৈরি করার প্রয়োজন হয়
লিনিয়ার স্টোরেজ বা জায়গা (Linear storage) \(O(n)\)
🪄 1D ডিপি রোলিং ভেরিয়েবল (1D DP rolling variables)
যখন dp[i] শুধুমাত্র শেষ k সংখ্যক স্টেটগুলোর উপর নির্ভর করে — তখন শুধু সেই k ভেরিয়েবলগুলোকেই মূলত সংরক্ষণ করে রাখুন
ধ্রুবক বা কন্সট্যান্ট স্টোরেজ (Constant storage) \(O(1)\)
🏠 হাউস রবারের গোলাকার বা সার্কুলার রূপ (House Robber circular variant)
আপনি চাইলে 0 নম্বর এবং n-1 নম্বর বাড়ি থেকে একসাথে লুট বা চুরি (rob) করতে পারবেন না — রবার বা চোরকে তাই [0..n-2] এবং [1..n-1]-এ বারবার রান বা পরিচালনা করুন, এবং এরপর এদের মধ্যে থাকা ম্যাক্স বা সর্বোচ্চ (max) মানটিকে বেছে নিন
দুটি লিনিয়ার পাস (Two linear passes) \(O(n)\)

ছোট কুইজ

সিঁড়িতে আরোহণ করা (climbing stairs) বা সিঁড়ি দিয়ে উপরে ওঠার এই সমস্যাটিতে (যেখানে একবারে ১ বা ২ ধাপ বা স্টেপ ওঠা যায়), আপনি মূলত কতটি উপায়ে ৫ নম্বর স্তরে বা ধাপে পৌঁছাতে পারবেন?

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

ডিপি প্যাটার্ন (DP Pattern)
একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
→
মেমোইজেশন বনাম ট্যাবুলেশন (Memoization vs Tabulation)
টপ-ডাউন (Top-down) হলো এমন এক বন্ধুর কাছে কল করা যে আবার অন্য এক বন্ধুকে কল করে। আর বটম-আপ (Bottom-up) হলো সারি ধরে ধরে একটি স্প্রেডশিট পূরণ করার মতো ব্যাপার।
→
0/1 ন্যাপস্যাক (0/1 Knapsack)
সর্বোচ্চ মূল্যের (value) জন্য একটি ব্যাগ বা স্যুটকেস প্যাক করুন — যেখানে প্রতিটি জিনিস বা আইটেম হয় পুরোপুরি নিতে হবে নতুবা একদমই নেওয়া যাবে না (all-or-nothing)
→