Summary
In this category, given a range alg[i,j]
, we need to identify a middle point k
and change the problem into alg[i,k] and alg[k+1, j]
.
Details
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 664. Strange Printer
Given a range alg[i,j]
, we could instantly print i
and reduce the problem to alg[i+1,j]
. Or we could hold i
and add it to k
, which means we print s[i,k]
all together with s[i]
, then the problem is reduced to alg[i + 1][k - 1]
and alg[k][j]
.
alg[i][j]
1. print i alone
1 + alg[i + 1][j]
2. i together with k i xxxx k xxx j
alg[i + 1][k - 1] + alg[k][j] if s[i] == s[k] for k in [i + 1, j]
// alg[i][i] = 1
// alg[i][i+1] = (s[i] == s[i + 1]) ? 1 : 2