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
| Trick | Difficulty | |
|---|---|---|
| LC 1049. Last Stone Weight II | DP in Linear Structures (NP) | 5 points |
| LC 375. Guess Number Higher or Lower II | DP in Intervals | 6-7 points |
| LC 1316. Distinct Echo Substrings | Rolling Hash + string_view or DP in Linear Structure + string_view | 6 points |
| LC 338. Counting Bits | Bit Manipulation + DP | 5 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 possibleLC 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]=4LC 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.