DP in Intervals (Dynamic)

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``````