(V.IMPORTANT) 2 types of interval DPs(MCM vs BB)

**Matrix Chain Multiplication (MCM) vs Burst Balloons (BB) — Full Annotated Guide**

---

## 🔍 Problem Setup:

### Matrix Chain Multiplication (MCM)

Given an array `arr` of size `n`, where:

* Matrix A\_i has dimension `arr[i-1] x arr[i]`
* Goal: Find the **minimum cost** to multiply matrices A1 \* A2 \* ... \* An

### Burst Balloons (BB)

Given an array `nums` representing balloon values:

* Bursting balloon at index `k` gives coins: `nums[i-1] * nums[k] * nums[j+1]`
* Goal: Find the **maximum coins** you can collect by bursting balloons in optimal order

---

## 1️⃣ Inclusive Interval in MCM

We define `solve(i, j)` to mean multiplying matrices A\_i to A\_j **inclusive**.

### Example:

Let `arr = [10, 20, 30, 40]`:

* A1: 10x20
* A2: 20x30
* A3: 30x40

To compute A1*A2*A3, we call `solve(1, 3)`

### Recurrence:

```cpp
solve(i, j) = min over k in [i, j-1] of:
    solve(i, k) + solve(k+1, j) + arr[i-1] * arr[k] * arr[j];
```

📊 Visual Representation:

```
arr:   [10   20   30   40]
       |----|----|----|
      A1   A2   A3

i = 1, j = 3 (we're multiplying A1 to A3)

k = 1:
┌─────────┐   ┌───────────────┐
│ A1      │ x │ (A2 x A3)     │
└─────────┘   └───────────────┘

k = 2:
┌─────────────┐   ┌─────────┐
│ (A1 x A2)   │ x │ A3      │
└─────────────┘   └─────────┘
```

✅ Why `k` is a Split Point in MCM

* `k` divides the chain into **two separate multiplication subproblems**
* You **solve each side recursively**, then multiply the resulting matrices
* `k` is **not** a matrix, it’s a **cut** between matrices

---

## 2️⃣ Exclusive Interval in Burst Balloons

We define `solve(i, j)` to mean bursting all balloons in the **exclusive range (i, j)**.

### Why Exclusive?

* Balloons at index `i` and `j` are used as the boundaries to compute coins when `k` is burst.
* So we must **leave them unburst** until we process a subinterval between them.
* This allows us to always safely say: `coins = nums[i] * nums[k] * nums[j]` because `i` and `j` are still intact.

### Recurrence:

```cpp
solve(i, j) = max over k in (i+1, j-1) of:
    nums[i] * nums[k] * nums[j] + solve(i, k) + solve(k, j);
```

📊 Visual Representation:

```
nums: [1   3   1   5   8   1]
        ^       ^
        i       j
        solve(i, j) => burst between i and j (exclusive)

k = i+1 to j-1
┌────────────┐   ┌────────────┐
│ solve(i,k) │ + │ solve(k,j) │ + nums[i]*nums[k]*nums[j]
└────────────┘   └────────────┘
```

✅ Why `k` is the Last to Burst in BB

* We assume `k` is the last balloon to be popped in range `(i, j)`
* This means the surroundings (`nums[i]` and `nums[j]`) are still unburst when `k` bursts
* That's why `k` is **not a divider** but a **last choice**

---

## 🔄 Inclusive vs Exclusive — Summary Table

| Feature                 | MCM                                  | Burst Balloons                        |
| ----------------------- | ------------------------------------ | ------------------------------------- |
| Interval Type           | Inclusive `[i, j]`                   | Exclusive `(i, j)`                    |
| Meaning of `solve(i,j)` | Multiply matrices A\_i to A\_j       | Burst all balloons between i and j    |
| Role of `k`             | Divider (split point)                | Last balloon to burst                 |
| Purpose of Split        | Divide chain into two subchains      | Defer k until subproblems are solved  |
| Cost Formula            | arr\[i-1] \* arr\[k] \* arr\[j]      | nums\[i] \* nums\[k] \* nums\[j]      |
| Recursive Merge         | Combine results of left × right      | Add result of left + right + burst(k) |
| Boundary Behavior       | No artificial padding usually needed | Padding with 1s at both ends often    |

---

## 🧠 Final Takeaways

### For MCM:

* In **MCM**, `solve(i, j)` = cost to multiply full chain A\_i to A\_j
* Use **inclusive intervals**
* `k` is a **divider** in `[i, j-1]`
* Recursively solve left and right, then combine with cost of multiplication

### For Burst Balloons:

* In **BB**, `solve(i, j)` = max coins by bursting balloons **between** i and j
* Use **exclusive intervals**
* `k` is the **last to burst** in `(i, j)`
* Coins are calculated after solving left and right, then bursting `k`

---

Let me know if you'd like this merged content exported as an updated PDF!