DP in Intervals (Break in Middle)

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