DP fundamentals: states and transitions · 2 of 3
Choosing the state
Choose a state that holds enough to write a transition: a yes-or-no value, a prefix with a take-or-skip choice, a fixed ending position, or two values per state.
- Longest Increasing Subsequence The slow and the fast solution, then two applications worked on one problem: non-intersecting segments and the minimum number of increasing sequences. usaco.guide (opens in a new tab)
- Longest increasing subsequence The O(n^2) table and how to restore the subsequence, the O(n \log n) version with binary search and another with data structures. cp-algorithms.com (opens in a new tab)