Skip to content

021 — Burst Balloons

Source

  • 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-টা ভাবো"

1. Problem in simple words

একটা 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

2. Which basic idea does this inherit from?

ভিত্তি 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 মোচড়।

3. What is the hidden math or logic?

লুকানো 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 করে।

4. Which data structure is needed?

একটা 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 ছোটগুলোর উপর নির্ভর করে।

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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]

fill by interval length (r - l) = 2, 3, 4, 5 ...

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

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

8. Example input and 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 = ... (নিচে test-এ যাচাই)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য ফাটানোর 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)

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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।

13. Thinking tweak

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

14. Step-by-step dry run

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. ✔

15. Python solution

# ---- 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!")

16. Line-by-line code explanation

  • 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 যাচাইয়ের জন্য।

17. Output walkthrough

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!।

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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 হয়ে যায়।

25. JavaScript solution (with test cases)

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

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 পড়ে)।

26. TypeScript solution (with test cases)

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-এ ধরা পড়ে।

27. কোথায় কাজে লাগে (real-world use)

  • 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।