- Solve and memoize subproblems first
Longest Increasing Subsequence
- Visualize
- Find appropriate subproblems (ex. the LIS starting at each element)
- Find dependencies in subproblems. Which subproblems does LIS(4) depend on?
LIS(4) = max(LIS(0), LIS(1), LIS(2), …)
- Recurse and memoize, or build memo table bottom-up