# 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``````