7 min read
development A walkthrough of "Longest Increasing Subsequence": why the natural DFS with backtracking solution blows up exponentially, and how dropping the in-progress sequence in favor of two indices makes the same recursion memoizable in O(n²) time.