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