Hard-to-Detect DP

Summary

In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve.

OJ

 TrickDifficulty
LC 1049. Last Stone Weight II DP in Linear Structures (NP)5 points
LC 375. Guess Number Higher or Lower II DP in Intervals6-7 points
LC 1316. Distinct Echo SubstringsRolling Hash + string_view or DP in Linear Structure + string_view6 points
LC 338. Counting BitsBit Manipulation + DP5 points

Details

LC 1049. Last Stone Weight II

Think of it in this way: we divide the numbers into two groups, and calculate the minimum difference between the sum of the groups.

alg[i][prev_sum] = 
    1. alg[i + 1][prev_sum + stones[i]]
    2. alg[i + 1][prev_sum]
// alg[n][prev_sum] = abs(sum - prev_sum - prev_sum)

LC 375. Guess Number Higher or Lower II

Once we identify this problem as a DP problem, it is not difficult. Given a number from 1 to n, actually we do not know which number to guess is the best, which indicates DP. After we guess one, the actual number might be larger or might be smaller. Here comes the MinMax.

alg[i][j] = min{ k + max(alg[i][k - 1], alg[k + 1][j]), for k in [i+1,...,j-1]}
//  alg[i][i] = 0, no need to pay for a single number
//  alg[i][i + 1] = i, pay as less as possible

LC 1316. Distinct Echo Substrings

It is not hard to get the rolling hash solution. Actually DP is a better way because it has no hash collision.

alg[i][j]
  1. s[i] == s[j]: 1 + alg[i + 1][j + 1]
  2. s[i] != s[j]: 0

// alg[i][j] has a echo string iif alg[i][j] >= (j - i)
// since "aaaaaa" has a[0][2]=4

LC 338. Counting Bits

There are several ways to connect the current number to a previous number.

Last Set Bit (rightmost set bit): alg[i]=alg[i&(i-1)]+1 . The trick i&(i-1)reset the last set bit.

Least Significant Bit (rightmost bit): alg[i]=alg[i>>1]+(i&1).

First Set Bit (leftmost set bit): alg[i]=alg[i-(1<<num_bit)]+1.

Leave a Reply

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