3. Backtracking and dynamic programming

views comments

Example 1: Text segmentation (Interpunctio verborum)

Example 2: Longest increasing subsequence

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

Related Media