3. Backtracking and dynamic programming
From Jeff Erickson
Example 1: Text segmentation (Interpunctio verborum)…Read more Less…
- A sequence of X's is either nothing or an X followed by a sequence of X's
- Where does the first word end?
- Recursive backtracking algorithm
- Index formulation
- Memo(r)ization: Remember previous results instead of recomputing them
- Dynamic progamming: Fill the memoization structure on purpose.
- Is this input number in the subsequence?
- An increasing sequence larger than x is either empty or a number y larger than x followed by an increasing sequence larger than y.
- Two-parameter recurrence -> memoize into 2d array
- single arrows = inner loop, double arrows = outer loop
- English specification + recurrence + evaluation order picture + time bound = full credit