§ 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 $A$, $B$ of size $n$, $m$.
• Naively, we have $2^n \times 2^m$ pairs of subsequences and we need to process each of them.
• How does the LCS DP solution manage to solve this in $O(nm)$?
• Key idea 1: create "filtration" of the problem $F_{i, j} \subseteq 2^n\times2^m$. At step $(i, j)$, consider the "filter" $F_{i, j}$containing all pairs of subsequences $(s \in 2^n, t \in 2^m)$ where maxix(s) \leq i and maxix(t) \leq j.
• These filters of the filtration nest into one another, so $F_{i, j} \subseteq F_{i', j'}$ iff $i \leq i'$ and $j \leq j'$.
• 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 $2^n \times 2^m$cleverly via filtration $F_{i, j}$ 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.