Problem link ও উৎস
- **Original source:** Classic interval DP exercise
- **Platform:** LeetCode —
- **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-টা ভাবো"
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `nums`, প্রত্যেকটা সংখ্যা একটা বেলুনের গায়ে লেখা। তুমি একে একে বেলুন ফাটাও। কোনো বেলুন `i` ফাটালে তুমি পাও `nums[left] * nums[i] * nums[right]` coin, যেখানে `left` আর `right` হলো `i`-এর তখনকার (এখনো-না-ফাটা) বাম ও ডান প্রতিবেশী। array-র দুই প্রান্তের বাইরে একটা করে কাল্পনিক বেলুন আছে যার মান 1। সব বেলুন ফাটিয়ে সর্বোচ্চ মোট কত coin পেতে পারো?
```text
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 {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা সারিতে দাঁড়ানো মানুষ একে একে চলে যাচ্ছে, আর কারো বিদায়ের সময় তার দাম নির্ভর করে তার তখনকার দুই পাশের প্রতিবেশীর উপর। কে আগে যাবে তা ভাবলে মাথা ঘোরে, কারণ প্রতিটা বিদায় বাকিদের প্রতিবেশী বদলে দেয়। বদলে জিজ্ঞেস করো: "এই দলটার মধ্যে সবার শেষে কে যাবে?" — সে যখন যাবে, তার দুই পাশে শুধু দলের বাইরের দুজন; আর তার বাঁ-দল ও ডান-দল আলাদা আলাদা হিসাব। উল্টো প্রশ্নটাই সব গিঁট খুলে দেয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 লাগে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য ফাটানোর order চেষ্টা করো।
```text
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:**
```text
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-র চাবি।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [3, 1, 5, 8]` → padding করে `a = [1, 3, 1, 5, 8, 1]`। `dp[l][r]` = open `(l, r)`-এর সেরা:
```text
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-এ ধাপে ধাপে {#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:
- k=1: `dp[0][1] + a[0]*a[1]*a[3] + dp[1][3] = 0 + 1*1*1 + 5 = 6`
- k=2: `dp[0][2] + a[0]*a[2]*a[3] + dp[2][3] = 5 + 1*5*1 + 0 = 10`
- max = 10
3. answer = `dp[0][3] = 10`
হাতে মিলিয়ে: 1 আগে ফাটাও (1*1*5 = 5), তারপর 5 (1*5*1 = 5) → 10. ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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 যাচাইয়ের জন্য।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-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 {#26-typescript-solution-with-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