Nearly any DP algorithm can be analyzed by multiplying the size of
the table by the time it takes to fill in a single cell of the table.
- segmentation: n table entries, O(n) time to fill in, O(n2) total.
- LCS: n m table entries, O(1) time to fill in, O(n m) total.
Next: Beam Search
Up: LONGEST COMMON SUBSEQUENCE
Previous: Algorithm