DP in Intervals (Dynamic)


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.


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]. Thennums[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

Leave a Reply

Your email address will not be published. Required fields are marked *