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

ইন্টারভালের উপর ডিপি (DP on Intervals)

প্রথমে ছোট ছোট অংশগুলোকে সমাধান করুন, তারপর সেগুলোকে বড় অংশে একত্রিত করে ফেলুন বা মার্জ (merge) করুন
time:\(O(n^3)\)space:\(O(n^2)\)

ধরুন আপনি একটি জিগস পাজল (jigsaw puzzle) জোড়া লাগানোর চেষ্টা করছেন। আপনি কখনোই পাজলটির প্রতিটি টুকরো একসাথে জোড়া লাগানোর চেষ্টা করবেন না — বরং আপনি এর কোণার ছোট অংশের কাজ আগে করবেন, তারপর সেগুলোকে আরও বড় অংশে একসাথে মেলাবেন, যতক্ষণ না পুরো ছবিটি ভালোভাবে জোড়া লাগছে বা তৈরি হচ্ছে। আর ঠিক এভাবেই ইন্টারভাল ডিপি (Interval DP) কাজ করে থাকে: এটি মূলত ছোট ছোট সাব-প্রোব্লেম বা উপ-সমস্যাগুলোকে আগে সমাধান করে, এরপর সেগুলোকে আরও বড় সমস্যার ভেতর একত্রিত করে নেয় বা কম্বাইন (combine) করে।

এ ধরনের সমস্যার স্টেট বা অবস্থাকে মূলত কোনো সিকোয়েন্স বা অনুক্রমের [i, j] রেঞ্জ (range) বা ইন্টারভাল (interval) দিয়ে চিহ্নিত করা হতে থাকে। এখানকার মূল রহস্য বা চাবিকাঠি হলো: কোনো একটি বড় বা লার্জ ইন্টারভালের সমাধান করার জন্য, আপনাকে অবশ্যই এর পেছনের সব সাব-ইন্টারভালগুলো বা উপ-পরিসরগুলোর সমাধান আগেই করে নিতে হবে। আর এই বিষয়টি আপনাকে একটি নির্দিষ্ট ক্রমে — অর্থাৎ, ছোট অংশ থেকে বড় অংশ সমাধান করতে বাধ্য করে দেয়।

প্যাটার্ন বা ধরণ (The Pattern)

স্টেট বা অবস্থা (State): dp[i][j] = এটি হলো কোনো সীমাবদ্ধ বা রেস্ট্রিক্টেড রেঞ্জ [i, j] এর ভেতর থাকা সমস্যার সবচেয়ে ভালো বা সর্বোত্তম (optimal) উত্তর।

ট্রানজিশন বা রূপান্তর (Transition): [i, j]-এর ভেতর যেকোনো একটি স্প্লিট পয়েন্ট বা ভাঙন বিন্দু বা বিভক্ত অংশ (split point) k কে নির্বাচন করুন এবং তারপর সেই সাব-ইন্টারভাল বা উপ-পরিসরগুলোর জন্য মূলত সমাধানগুলোকে একত্রে যুক্ত বা কম্বাইন (combine) করুন — যা সাধারণত [i, k] এবং [k+1, j], অথবা [i, k-1] + k + [k+1, j] হয়ে থাকে।

পূরণ করার ক্রম (Fill order): বাইরের লুপটি বা সাইকেলটি মূলত l = 1, 2, …, n দৈর্ঘ্যের হয়ে থাকে। ভেতরের বা ইনার (inner) লুপটি i এর স্টার্টিং পজিশন বা ভিত্তি অবস্থানের (starting positions) উপর কাজ করে (যেখানে j = i + l - 1 নির্ধারণ করা থাকে)। একদম ভেতরের (Innermost) লুপটি মূলত k-এর স্প্লিট পয়েন্টগুলোর (split points) উপর কাজ করে।

বেস কেস বা ভিত্তি (Base case): dp[i][i] — যা মূলত একটি সিঙ্গেল ইলিমেন্ট বা একক উপাদানকে বোঝায়, এবং এটা সাধারণত 0 বা অতি সাধারণ (trivial) কোনো একটি মান বা স্টেট হয়ে থাকে।

বার্স্ট বেলুনস বা ফাটানো বেলুনগুলো — এর ক্যানোনিকাল টুইস্ট বা মোড় (Burst Balloons — The Canonical Twist)

ধরুন, আপনার কাছে ঠিক n সংখ্যক বেলুন আছে, এবং প্রতিটির একটি করে মান বা ভ্যালু (value) আছে। বেলুন i ফাটালে আপনি মূলত nums[i-1] × nums[i] × nums[i+1] কয়েন বা মুদ্রা পাবেন (যাতে এর প্রতিবেশী বা নেইবারস (neighbors) এবং সীমানায় কিছু ভার্চুয়াল (virtual) 1s থাকে)। এবার আপনাকে ঠিক এই সর্বমোট কয়েন বা সম্পদের পরিমাণকে সর্বোচ্চ বা ম্যাক্সিমাইজ (Maximize) করতে হবে।

এর চালাকি বা রিফ্রেমটি (The clever reframe): "কোন বেলুনটিকে প্রথমে ফাটাতে হবে" এটি জিজ্ঞেস করার পরিবর্তে বরং এটি জিজ্ঞেস করুন "[i, j] এর ভেতরের কোন বেলুনটি সবার শেষে বা সবার শেষে ফাটে?" যখন কোনো বেলুন k সবার শেষে ফাটে বা ধ্বংস হয় তখন এর [i, j] এর ভেতর থাকা অন্যান্য সমস্ত বেলুন আগেই ফেটে যায় — যার ফলে এই বেলুন k-এর প্রতিবেশীরা বা নেইবারগুলো একদম ফিক্সড বা নির্দিষ্ট হিসেবে থেকে যায়। যা আমাদেরকে এই ফলাফলটি দেয়: dp[i][j] = max over k of (dp[i][k-1] + nums[i-1]×nums[k]×nums[j+1] + dp[k+1][j])।

স্টোন মার্জ বা পাথর জোটবদ্ধ করা (Stone Merge)

পাথরের n সংখ্যক স্তূপকে একত্রে যুক্ত করুন (শুধুমাত্র অ্যাডজাসেন্ট বা সংলগ্ন পাথরগুলোই)। একেকটি একত্রীকরণ বা মার্জের (merge) ব্যয় বা কস্ট (Cost) = একত্রিত করা ওই গ্রুপের মোট পাথর সংখ্যা। এর মোট খরচ বা টোটাল কস্টকে মূলত সর্বনিম্নে (Minimize) বা কম স্থানে নিয়ে আসুন। এই dp[i][j] = i..j-কে একত্রে একটি স্তূপে পরিণত করার জন্য প্রয়োজনীয় সবচেয়ে কম বা সর্বনিম্ন খরচ। এখানে সমস্ত স্প্লিট বা বিভাজনগুলোর (splits) প্রয়োগ চেষ্টা করুন, এবং এর দুই অর্ধেককে একত্রিত বা কম্বাইনিং করার প্রিফিক্স-সাম কস্ট বা প্রেফিক্স-সাম খরচ (prefix-sum cost) যোগ করুন।

প্যালিনড্রোম পার্টিশনিং বা বিভাজন (Palindrome Partitioning)

ক্ষুদ্রতম সংখ্যক কাট বা বিভাজন ব্যবহার করে একটি স্ট্রিং-কে (string) এমনভাবে বিভক্ত করুন যাতে এর প্রতিটি খণ্ড বা পিস (piece) একেকটি প্যালিনড্রোম (palindrome) হয়ে থাকে। এটি আসলে 1D ডিপি (1D DP) এর ছদ্মবেশে থাকা একটি সমস্যা: যেখানে dp[i] = মূলত s[0..i] এর সর্বনিম্ন কাট বা মিনিমাম কাটগুলোকে (min cuts) বোঝায়। সব ধরনের j ≤ i ব্যবহার করে চেষ্টা করুন যেখানে s[j..i] একটি প্যালিনড্রোম: আর dp[i] = min(dp[j-1] + 1)। এখানে প্যালিনড্রোমিক সাবস্ট্রিংগুলোকে আলাদাভাবে প্রি-কম্পিউট (pre-compute) করে নিন।

দ্রষ্টব্য: বার্স্ট বেলুনসের (Burst Balloons) ওই 'সর্বশেষ বেলুন' বা 'last balloon'-এর ট্রিকটি বেশ ক্লাসিক (classic) একটি ট্রিক (trick): একটি ইন্টারভাল বা ব্যাপ্তির ভেতর শেষে কী ঘটবে সে বিষয়ে যুক্তি দেখানো বা রিজনিং (reasoning) করা বেশি সহজ হয়ে থাকে কারণ এর সীমানাগুলো মূলত নির্দিষ্ট বা ফিক্সড (fixed) থাকে — অপরদিকে, প্রথমে কী ঘটবে এই প্রশ্নের আশেপাশে ঘোরাঘুরি বা চিন্তা ভাবনা করা মূলত বাকি স্ট্রাকচার বা গঠনটিকে বিশৃঙ্খল বা ক্যাওটিক (chaotic) অবস্থায় ছেড়ে দেয়।

বার্স্ট বেলুনস (Burst Balloons) — ইন্টারভাল ডিপি (interval DP)

def max_coins(nums):
    nums = [1] + nums + [1]  # virtual boundary balloons
    n = len(nums)
    dp = [[0]*n for _ in range(n)]
    # i and j are indices within the padded array
    for length in range(2, n):
        for i in range(0, n - length):
            j = i + length
            for k in range(i+1, j):
                dp[i][j] = max(dp[i][j],
                    dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j])
    return dp[0][n-1]


print(max_coins([3, 1, 5, 8]))  # 167
print(max_coins([1, 5]))        # 10
Output
167
10

Complexity

⏱️ সময় (Time)
\(O(n^2)\) ইন্টারভাল বা ব্যাপ্তি × ইন্টারভাল প্রতি \(O(n)\) স্প্লিট পয়েন্ট (split points) — অর্থাৎ তিনটি করে নেস্টেড বা ভেতরের লুপ (nested loops)
কিউবিক বা ত্রিঘাত (Cubic) \(O(n^3)\)
📊 জায়গা বা স্পেস (Space)
সমস্ত সম্ভাব্য ইন্টারভালের বা ব্যাপ্তির জন্য মূলত dp[n][n] আকারের একটি টেবিল বা ছক ব্যবহার করা হয়
কোয়াড্র্যাটিক বা দ্বিঘাত (Quadratic) \(O(n^2)\)
📐 ফাইল অর্ডারের বা ক্রমের ওভারহেড (Fill order overhead)
বাইরে (Outer): n দৈর্ঘ্য; মাঝখানে (middle): n আরম্ভের অবস্থান বা শুরু করার পজিশন; ভেতরে (inner): n স্প্লিট পয়েন্ট বা বিভক্তিগুলো
দৈর্ঘ্যের উপর ভিত্তি করে (By length) বাইরের দিকে \(O(n^2)\) (outer) + ভিতরের দিকে \(O(n)\) (inner)
🔢 ম্যাট্রিক্স চেইন (Matrix Chain) MCM (একই প্যাটার্ন বা ধরন)
এই ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন (Matrix chain multiplication) মূলত ইন্টারভাল ডিপি-র (interval DP) একটি বিশেষ অবস্থা বা স্পেশাল কেস (special case)
বাকিগুলোর মতোই অভিন্ন জটিলতা বা কমপ্লেক্সিটি (Identical complexity) \(O(n^3)\)

ছোট কুইজ

বার্স্ট বেলুনস (Burst Balloons) এর ক্ষেত্রে, একটি ইন্টারভাল বা ব্যাপ্তির (interval) মধ্যে থাকা সবার শেষের বেলুনটি (LAST balloon) ফেটে যাওয়ার ব্যাপারে আমরা কেন চিন্তা করি — আর কেন প্রথমটির নিয়ে ভাবি না?

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

ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন (Matrix Chain Multiplication)
যে ক্রমে আপনি ম্যাট্রিক্স গুণ করেন তা অত্যন্ত গুরুত্বপূর্ণ — সবচেয়ে কম খরচের বা চিপেস্ট (cheapest) ক্রমটি খুঁজে বের করুন
→
ডিপি প্যাটার্ন (DP Pattern)
একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
→