## Summary

Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed.

## Details

#### Minimum Cost to Merge Stones I

There are N piles of stones arranged in a row. The i-th pile has stones[i] stones. A move consists of merging 2 consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these 2 piles. Find the minimum cost to merge all piles of stones into one pile.

Think backwards. Consider the last pile in range `nums[i,...,j]`

is formed by “Super Stone” `nums[i,...,k]`

and “Super Stone” `nums[k + 1,...,j]`

. Here “Super Stone” `nums[i,...,k]`

means these stones will form into a single stone.

`alg[i][j]=min(alg[i][j],alg[i][k]+alg[k+1][j]+sum[i][j]), k in [i, j - 1]`

An interesting variance of this problem is that any two stones can be merged. In this case, we can greedily choose smaller stones to merge together, which becomes a Huffman Code problem.

#### LC 1000. Minimum Cost to Merge Stones II

This problem involves another dimension and it also needs to be thought backwards. Consider the last pile in range `nums[i,...,j]`

is formed by `K`

piles of stones. `nums[i,...,l]`

forms one pile and `nums[l + 1,...,j]`

forms `K-1`

piles.

```
alg[i][j][k] (k >= 2) =
min{ alg[i][l][1] + alg[l + 1][j][k - 1] for l in [i, ... j - 1]}
// Note that is not min{ alg[i][l][1] + alg[l + 1][j][k - 1] + sum[i][j]}! Since forming k piles does not need to pay.
alg[i][j][1] = alg[i][j][k] + sum[i][j]
// alg[i][i][1] = 0
// sum[i][j]: prefix_sum[j] - ((i - 1 >= 0) ? prefix_sum[i - 1] : 0)
```

#### LC 1130. Minimum Cost Tree From Leaf Values

Think backwards. Consider `nums[k]`

is the last number in range `nums[i,...,j]`

. `nums[i,...,k]`

forms the left subtree, and `nums[k + 1,...,j]`

forms the right subtree.

```
max_num[i][j] = max(max_num[i + 1][j - 1], nums[i], nums[j])
alg[i][j] = min {alg[i][k] + alg[k + 1][j] + max_num[i][k] * max_num[k + 1][j], for k in [i, ..., j - 1]}
// alg[i][i] = 0
// alg[i][i + 1] = nums[i] * nums[i + 1]
```

#### LC 312. Burst Balloons

Think backwards. Consider `nums[k]`

is the last ballon in range `nums[i+1,...,j-1]`

. Then`nums[i+1,...,k-1]`

should be bursted out, and `nums[k+1,...,j-1]`

should also be bursted out. `nums[i+1,...,k-1]`

will be `alg[i][k]`

.

```
// pad nums => {1, nums[0], ..., nums[n - 1], 1}
alg[i][j] = max { nums[i] * nums[j] * nums[k] + alg[i][k] + alg[k][j], for k in [i + 1, ..., j - 1]}
// alg[i][i] = INT_MIN
// alg[i][i + 1] = INT_MIN
```