§ LCS DP: The speedup is from filtration
- I feel like I finally see where the power of dynamic programming lies.
- Consider the longest common subsequence problem over arrays , of size , .
- Naively, we have pairs of subsequences and we need to process each of them.
- How does the LCS DP solution manage to solve this in ?
- Key idea 1: create "filtration" of the problem . At step , consider the "filter" containing all pairs of subsequences where
maxix(s) \leq i and
maxix(t) \leq j.
- These filters of the filtration nest into one another, so iff and .
- Key idea 2: The value of
max LCS(filter) is (a) monotonic, and (b) can be computed efficiently from the values of lower filtration. So we have a monotone map from the space of filters to the solution space, and this monotone map is efficiently computable, given the values of filters below this in the filtration.
- This gives us a recurrence, where we start from the bottom filter and proceed to build upward.
- See that this really has nothing to do with recursion. It has to do with problem decomposition . We decompose the space cleverly via filtration such that
max LCS(F[i, j]) was efficiently computable.
- To find a DP, think of the entire state space, then think of filtrations, such that the solution function becomes a monotone map, and the solution function is effeciently computable given the values of filters below it.