021 — Burst Balloons

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: Classic interval DP exercise
• Platform: LeetCode — https://leetcode.com/problems/burst-balloons/
• Topic: dynamic programming (interval DP)
• Difficulty: Hard
• Pattern: Interval DP
• Basic idea inherited from: patterns.md-এর interval teaser — dp[l][r] একটা range-এর উত্তর, fill order interval-এর length অনুযায়ী; signature trick: "প্রথম নয়, LAST balloon-টা ভাবো"

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা array nums, প্রত্যেকটা সংখ্যা একটা বেলুনের গায়ে লেখা। তুমি একে একে বেলুন ফাটাও। কোনো বেলুন i ফাটালে তুমি পাও nums[left] * nums[i] * nums[right] coin, যেখানে left আর right হলো i-এর তখনকার (এখনো-না-ফাটা) বাম ও ডান প্রতিবেশী। array-র দুই প্রান্তের বাইরে একটা করে কাল্পনিক বেলুন আছে যার মান 1। সব বেলুন ফাটিয়ে সর্বোচ্চ মোট কত coin পেতে পারো?

উদাহরণ

nums = [3, 1, 5, 8]
এক ভালো order: 1 -> 5 -> 3 -> 8
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167

Input ও output

উদাহরণ

Input : nums = [3, 1, 5, 8] -> Output: 167
Input : nums = [1, 5]       -> Output: 10   (5 আগে: 1*5*1=5; তারপর 1: 1*1*1=1 -> 6;
                                             বা 1 আগে: 1*1*5=5; তারপর 5: 1*5*1=5 -> 10)
Input : nums = [7]          -> Output: 7    (1*7*1)

Edge case 1: nums = []       -> Output: 0
Edge case 2: nums = [1, 1]   -> Output: 2
Edge case 3: nums = [9, 76]  -> Output: 760
  9 আগে: 1*9*76 + 1*76*1 = 684 + 76 = 760
  76 আগে: 9*76*1 + 1*9*1 = 684 + 9 = 693

চেনা উদাহরণে বোঝা

ভাবো একটা সারিতে দাঁড়ানো মানুষ একে একে চলে যাচ্ছে, আর কারো বিদায়ের সময় তার দাম নির্ভর করে তার তখনকার দুই পাশের প্রতিবেশীর উপর। কে আগে যাবে তা ভাবলে মাথা ঘোরে, কারণ প্রতিটা বিদায় বাকিদের প্রতিবেশী বদলে দেয়। বদলে জিজ্ঞেস করো: "এই দলটার মধ্যে সবার শেষে কে যাবে?" — সে যখন যাবে, তার দুই পাশে শুধু দলের বাইরের দুজন; আর তার বাঁ-দল ও ডান-দল আলাদা আলাদা হিসাব। উল্টো প্রশ্নটাই সব গিঁট খুলে দেয়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি patterns.md-এর interval DP family। আগের সব DP-তে state ছিল prefix (dp[i]) বা grid-cell (dp[r][c]); এখানে state একটা interval dp[l][r] — l..r range-এর সব বেলুন ফাটানোর সেরা উত্তর। নতুন reflex: কোনটা প্রথম ফাটে তা না ভেবে, একটা range-এ সবার শেষে কোন বেলুনটা ফাটে তা ভাবা — এটাই interval DP-র signature মোচড়।

ভেতরের যুক্তি

লুকানো logic উল্টোদিক থেকে ভাবা। একটা range (l, r) (exclusive bound)-এ যদি k হয় সবচেয়ে শেষে ফাটা বেলুন, তখন k ফাটার মুহূর্তে তার দুই পাশে শুধু boundary বেলুন nums[l] আর nums[r] দাঁড়িয়ে (ভেতরের বাকি সব আগেই গেছে)। তাই k-এর জন্য পাওয়া coin nums[l] * nums[k] * nums[r] — একটা নির্দিষ্ট মান। আর k-এর বাঁ অংশ (l, k) ও ডান অংশ (k, r) তখন স্বাধীন subproblem, কারণ k এখনো আছে বলে তারা একে অপরকে প্রভাবিত করে না। এই "last balloon" বাছাই subproblem-গুলোকে decouple করে।

কী দিয়ে তথ্য রাখব

একটা 2D array dp, size (n+2) x (n+2), যেখানে nums-কে দুই প্রান্তে 1 দিয়ে padding করা হয়। dp[l][r] = open interval (l, r)-এর ভেতরের সব বেলুন ফাটানোর max coin। fill order interval-এর length অনুযায়ী — ছোট interval আগে, বড় পরে — কারণ বড় interval ছোটগুলোর উপর নির্ভর করে।

এটি কেন উপযুক্ত

State-এ একটা পুরো range ধরতে হয়, কারণ "শেষে কোন বেলুন ফাটে" সিদ্ধান্তটা range-টাকে দুই সাব-range-এ ভাঙে — দুই endpoint-ই জানা লাগে। তাই দুই index (l, r) দিয়ে state। padding boundary দিয়ে edge-effect ("প্রান্তের প্রতিবেশী 1") এমনিই handle হয়, আলাদা if-else লাগে না।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য ফাটানোর order চেষ্টা করো।

উদাহরণ

best(remaining_balloons):
    if empty: return 0
    ans = 0
    for each balloon i in remaining:           # i প্রথমে ফাটে
        gain = leftNeighbor * nums[i] * rightNeighbor
        ans = max(ans, gain + best(remaining - i))
    return ans
answer = best(all)

কোথায় বেশি কাজ হচ্ছে

সব order চেষ্টা করা মানে O(n!) permutation — 12-13 বেলুনেই অসম্ভব। আর "প্রথমে কে ফাটে" ধরলে subproblem-গুলো independent হয় না (একটা ফাটলে বাকিদের প্রতিবেশী বদলায়), তাই সরল memoization-ও খাটে না। এই decoupling সমস্যাটাই "last balloon" reframing সমাধান করে।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একটা range-এ শেষে কোন বেলুন ফাটে সেটা ঠিক করলে দুই পাশের সাব-range সম্পূর্ণ স্বাধীন হয়ে যায় — কারণ ওই শেষ বেলুনটা তখনও দাঁড়িয়ে, দুই অংশকে আলাদা রাখছে। এই independence-ই overlapping subproblem-কে বৈধ করে আর O(n!)-কে O(n³)-এ নামায়।

আরও কম কাজে সমাধান

State (শব্দে): dp[l][r] = padding-করা array-এর open interval (l, r) — অর্থাৎ l ও r বাদ দিয়ে কঠোরভাবে এদের মাঝের সব বেলুন — ফাটিয়ে পাওয়া সম্ভব maximum coin। l আর r নিজেরা boundary, এখনো অক্ষত।

Transition:

উদাহরণ

dp[l][r] = max over k in (l+1 .. r-1) of
           dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]
# k = এই interval-এ সবার শেষে ফাটা বেলুন

Base case: dp[l][r] = 0 যখন r <= l + 1 (মাঝে কোনো বেলুন নেই)।

Answer location: dp[0][n+1] — পুরো padding-করা array।

Fill order: interval-এর length (r - l) ছোট থেকে বড়; প্রতিটা length-এ সব l slide করো। এতে dp[l][k] আর dp[k][r] (ছোট interval) সবসময় আগেই computed।

ভাবনার পরিবর্তন

মোচড়: স্বাভাবিক প্রবৃত্তি "কোন বেলুন প্রথমে ফাটাব" — কিন্তু সেটা subproblem-গুলোকে জড়িয়ে ফেলে, কারণ প্রথম ফাটানো প্রতিবেশী বদলায়। উল্টে জিজ্ঞেস করো "এই range-এ সবার শেষে কোনটা ফাটবে।" শেষ বেলুনটা তো পুরো প্রক্রিয়া জুড়ে দাঁড়িয়ে থাকে, তাই সে দুই পাশকে আলাদা করে রাখে — subproblem decouple হয়ে যায়। এই "ভাবো শেষ সিদ্ধান্তটা" অনেক interval DP-র চাবি।

ছবিতে বোঝা

nums = [3, 1, 5, 8] → padding করে a = [1, 3, 1, 5, 8, 1]। dp[l][r] = open (l, r)-এর সেরা:

উদাহরণ

a = [1, 3, 1, 5, 8, 1]    (index 0..5; 0 আর 5 হলো boundary 1)

dp[l][r] = max over k in (l+1 .. r-1) of
           dp[l][k] + a[l]*a[k]*a[r] + dp[k][r]
                       ^^^^^^^^^^^^^^
                       k সবার শেষে ফাটে: পাশে a[l], a[r]

এই input-এ fill order: (r - l) = 2, 3, 4, 5

ছোট interval (length 2, ভেতরে 1 বেলুন) আগে ভরে,
তারপর তাদের ব্যবহার করে বড় interval; answer = dp[0][n+1]

প্রতিটা (l, r)-এ ভেতরের প্রতিটা k-কে "শেষ-ফাটা" ধরে চেষ্টা করো; সবচেয়ে বড় মোট নাও।

ছোট input-এ ধাপে ধাপে

nums = [1, 5] → a = [1, 1, 5, 1] (index 0..3)। dp[l][r], fill by length:

1. length 2 (ভেতরে 1 বেলুন): dp[0][2] (k=1): 0 + a[0]*a[1]*a[2] + 0 = 1*1*5 = 5; dp[1][3] (k=2): 1*5*1 = 5
2. length 3 (ভেতরে 2 বেলুন): dp[0][3], k সম্ভব 1 বা 2:
3. k=1: dp[0][1] + a[0]*a[1]*a[3] + dp[1][3] = 0 + 1*1*1 + 5 = 6
4. k=2: dp[0][2] + a[0]*a[2]*a[3] + dp[2][3] = 5 + 1*5*1 + 0 = 10
5. max = 10
6. answer = dp[0][3] = 10

হাতে মিলিয়ে: 1 আগে ফাটাও (115 = 5), তারপর 5 (151 = 5) → 10. ✔

কোড ও ব্যাখ্যা

Python

Python

# ---- way 1: top-down memoization on intervals ----
def burst_memo(nums):
    a = [1] + nums + [1]
    n = len(a)
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def solve(l, r):                         # open interval (l, r)
        if r <= l + 1:
            return 0
        best = 0
        for k in range(l + 1, r):            # k সবার শেষে ফাটে
            gain = solve(l, k) + a[l] * a[k] * a[r] + solve(k, r)
            if gain > best:
                best = gain
        return best
    return solve(0, n - 1)

# ---- way 2: bottom-up tabulation, fill by interval length ----
def burst_tab(nums):
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):               # (r - l) = 2, 3, ..., n-1
        for l in range(0, n - length):
            r = l + length
            best = 0
            for k in range(l + 1, r):
                gain = dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]
                if gain > best:
                    best = gain
            dp[l][r] = best
    return dp[0][n - 1]

# ---- tests ----
def brute(nums):                             # O(n!) reference (ছোট input-এর জন্য)
    def rec(arr):
        if not arr:
            return 0
        best = 0
        for i in range(len(arr)):
            left = arr[i - 1] if i - 1 >= 0 else 1
            right = arr[i + 1] if i + 1 < len(arr) else 1
            gain = left * arr[i] * right + rec(arr[:i] + arr[i + 1:])
            best = max(best, gain)
        return best
    return rec(nums)

cases = [
    ([3, 1, 5, 8], 167),
    ([1, 5], 10),
    ([7], 7),
    ([], 0),
    ([1, 1], 2),
]
for nums, want in cases:
    assert burst_memo(nums) == want, (nums, burst_memo(nums))
    assert burst_tab(nums) == want, (nums, burst_tab(nums))

# দুই DP version-কে brute-force-এর সাথে মেলাও (ছোট random-ধাঁচের input)
for nums in [[9, 76], [2, 3, 4], [5, 1, 1, 5], [4]]:
    ref = brute(nums)
    assert burst_memo(nums) == ref, (nums, burst_memo(nums), ref)
    assert burst_tab(nums) == ref, (nums, burst_tab(nums), ref)

print("সব test pass!")

কোডের প্রতিটি অংশ

• burst_memo: a = দুই প্রান্তে 1 দিয়ে padding; solve(l, r) open interval-এর সেরা; ভেতরের প্রতিটা k-কে "শেষ-ফাটা" ধরে gain মাপে; lru_cache repeated (l, r) cache করে।
• burst_tab: একই recurrence, কিন্তু interval-length-অনুসারে নিচ থেকে ভরা — length 2 থেকে বাড়ে, প্রতিটায় সব l, ভেতরে সব k; answer dp[0][n-1]।
• brute: O(n!) reference যা প্রতিটা বেলুনকে "প্রথমে ফাটা" ধরে recurse করে; শুধু ছোট input-এ DP-গুলোর correctness যাচাইয়ের জন্য।

Output মিলিয়ে দেখা

cases-এ পাঁচটা সরাসরি input: classic [3,1,5,8] (167), [1,5] (10), single (7), খালি (0), [1,1] (2)। তারপর চারটা ছোট array-তে দুই DP version-কে O(n!) brute-এর সাথে মিলিয়ে দেখা হয় — এটাই recurrence ঠিক আছে তার শক্ত প্রমাণ। সব pass হলে শেষে print: সব test pass!।

JavaScript ও test cases

Interval DP, "last balloon" trick; padding করে dp[l][r], fill by length, ভেতরের brute দিয়ে cross-check।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[l][r] = open interval (l, r)-এর max coin; fill by interval length
function maxCoins(nums) {
  const a = [1, ...nums, 1];                   // দুই প্রান্তে boundary 1
  const N = a.length;
  const dp = Array.from({ length: N }, () => new Array(N).fill(0));
  for (let len = 2; len < N; len++) {          // (r - l) = 2, 3, ...
    for (let l = 0; l + len < N; l++) {
      const r = l + len;
      let best = 0;
      for (let k = l + 1; k < r; k++) {        // k সবার শেষে ফাটে
        const gain = dp[l][k] + a[l] * a[k] * a[r] + dp[k][r];
        if (gain > best) best = gain;
      }
      dp[l][r] = best;
    }
  }
  return dp[0][N - 1];
}
// O(n!) reference (ছোট input-এর জন্য): প্রতিটা বেলুনকে "প্রথমে ফাটা" ধরে
function brute(nums) {
  if (nums.length === 0) return 0;
  let best = 0;
  for (let i = 0; i < nums.length; i++) {
    const left = i - 1 >= 0 ? nums[i - 1] : 1;
    const right = i + 1 < nums.length ? nums[i + 1] : 1;
    const rest = nums.slice(0, i).concat(nums.slice(i + 1));
    best = Math.max(best, left * nums[i] * right + brute(rest));
  }
  return best;
}
// ---- test cases (example + edge) ----
const cases = [
  [[3, 1, 5, 8], 167],
  [[1, 5], 10],
  [[7], 7],
  [[], 0],                                     // খালি edge
  [[1, 1], 2],
];
for (const [nums, want] of cases) {
  assert(maxCoins(nums) === want, "burst " + nums);
}
// DP-কে brute-force-এর সাথে মেলাও (ছোট input, recurrence-এর শক্ত প্রমাণ)
for (const nums of [[9, 76], [2, 3, 4], [5, 1, 1, 5], [4]]) {
  assert(maxCoins(nums) === brute(nums), "vs-brute " + nums);
}
console.log("সব JS test pass!");

JS টীকা: 2D DP grid বানাতে Array.from({length: N}, () => new Array(N).fill(0)) — .fill(new Array(N)) সব row এক reference করিয়ে দিত (interval DP-তে মারাত্মক)। padding করতে [1, ...nums, 1] (spread) — nums-এর দুই প্রান্তের প্রতিবেশী 1, না বসালে প্রান্তের গুণফল ভুল। fill order অবশ্যই interval-length অনুযায়ী, সাধারণ row/column নয় (নাহলে ছোট interval এখনো computed না থাকায় garbage পড়ে)।

TypeScript ও test cases

TypeScript

function maxCoins(nums: number[]): number {
  const a: number[] = [1, ...nums, 1];
  const N: number = a.length;
  const dp: number[][] = Array.from({ length: N }, () => new Array<number>(N).fill(0));
  for (let len = 2; len < N; len++) {
    for (let l = 0; l + len < N; l++) {
      const r: number = l + len;
      let best = 0;
      for (let k = l + 1; k < r; k++) {
        const gain: number = dp[l][k] + a[l] * a[k] * a[r] + dp[k][r];
        if (gain > best) best = gain;
      }
      dp[l][r] = best;
    }
  }
  return dp[0][N - 1];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number[], number]> = [
  [[3, 1, 5, 8], 167],
  [[1, 5], 10],
  [[7], 7],
  [[], 0],
  [[1, 1], 2],
];
for (const [nums, want] of cases) expect(maxCoins(nums), want, "burst");
console.log("সব TS test pass!");

TS টীকা: dp: number[][] ও new Array<number>(N) typing দিয়ে interval-table-এর element-type locked; a: number[] padding-array স্পষ্ট। cases: Array<[number[], number]> tuple-type input/expected জোড়া নিশ্চিত করে — খালি array edge সহ ভুল গঠন compile-time-এ ধরা পড়ে।

খরচ ও সাধারণ ভুল

সময়

দুই DP version-ই O(n³) — O(n²) interval, প্রতিটায় ভেতরের k-loop O(n)। (Naive ছিল O(n!)।)

অতিরিক্ত জায়গা

• Memoization: O(n²) cache + O(n) recursion depth।
• Tabulation: O(n²) — dp table।

যে ভুলগুলো এড়াতে হবে

• "প্রথম ফাটা" দিয়ে ভাবা — তখন subproblem independent হয় না, recurrence ভুল হয়; "শেষ ফাটা" ভাবতে হবে।
• boundary padding ভুলে যাওয়া — nums-এর দুই প্রান্তের প্রতিবেশী 1, এটা [1] + nums + [1] দিয়ে না বসালে প্রান্তের গুণফল ভুল হয়।
• fill order interval-length-এর বদলে সাধারণ row/column করা — তখন বড় interval ভরার সময় ভেতরের ছোট interval এখনো computed নয়, garbage পড়ে।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: ../patterns.md-এর "Interval DP (teaser)" — dp[l][r], length-অনুযায়ী fill, আর "LAST element processed" reframing। এই note সেই teaser-টাকেই একটা সম্পূর্ণ runnable সমাধানে পরিণত করে।

পরের অনুশীলন

• Minimum Cost to Merge Stones — https://leetcode.com/problems/minimum-cost-to-merge-stones/
• Remove Boxes (কঠিন interval DP, extra dimension) — https://leetcode.com/problems/remove-boxes/
• Strange Printer (interval merge) — https://leetcode.com/problems/strange-printer/

কৌশলটি মনে রাখুন

Interval DP: state dp[l][r] = একটা range-এর উত্তর; transition-এ range-এর ভেতরের একটা split/last-element k বেছে দুই সাব-range + একটা যোগফল মেলাও; fill order interval-এর length অনুযায়ী। "প্রথম নয়, শেষ সিদ্ধান্তটা ভাবো" — এই reframing matrix-chain, merge-stones, burst-ধাঁচের সব সমস্যায় ফেরে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "Burst Balloons = interval DP, last-balloon trick।" State dp[l][r] = open (l, r)-এর max coin, transition: ভেতরের প্রতিটা k-কে শেষ-ফাটা ধরে dp[l][k] + a[l]*a[k]*a[r] + dp[k][r]-এর max, fill by length, answer dp[0][n+1]। মনে রেখো: "শেষে কোনটা" জিজ্ঞেস করলেই subproblem decouple হয়ে যায়।

কোথায় কাজে লাগে

• Matrix-chain multiplication: কোন ক্রমে গুণ করলে মোট খরচ ন্যূনতম — classic interval DP (একই last/split reframing)।
• Optimal merge / file combining: ছোট অংশ একে একে merge করার সবচেয়ে সস্তা ক্রম (merge-stones ধরনের)।
• Polygon triangulation: একটা polygon-কে ত্রিভুজে ভাগ করার ন্যূনতম-খরচ উপায়।
• Optimal BST / parsing cost: সাব-range-ভিত্তিক খরচ মিনিমাইজ (অভিধান-search বা grammar parsing খরচ)।
• Sequence "remove for max reward": এমন order বের করা যেখানে প্রতিটা সরানোর reward প্রতিবেশী-নির্ভর (এই problem নিজেই)।

মূল pattern: state dp[l][r] = একটা range-এর উত্তর; "প্রথম নয়, শেষ সিদ্ধান্তটা ভাবো" দিয়ে subproblem decouple; fill order interval-length অনুযায়ী।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।