State-Machine

One-dimensional DP, state-machine DP, DP with a monotonic deque, interval scheduling DP after sorting, deduplicated subsequence counting, and DP-tagged problems where an observation or greedy is faster

LeetCode 1220 note: state machine DP on the last vowel; turn “what may follow x” around into “what may precede x”

LeetCode 1320 note: after typing word[i], one finger is always on word[i], so the state is only the other finger’s position; dp[other] is the least distance with the other finger at other

LeetCode 2912 note: many cells, but only four classes relative to the destination (itself, same row, same column, neither); each class’s total moves together in O(k)

LeetCode 552 note: state machine DP with state “A used × trailing L run”, 6 states; each day’s P, A or L picks the next state

LeetCode 1411 note: a row’s colorings come in two patterns, ABA (ends match) and ABC (all different), 6 each; the next row gives ABA → 3 ABA + 2 ABC and ABC → 2 ABA + 2 ABC

LeetCode 3952 note: each token moves left at most once, so the state is whether this index’s token moved left; moving only helps if the index to the left was not already covered

LeetCode note for Best Time to Buy and Sell Stock with Transaction Fee, rebuilt from the original learning note

LeetCode note for Best Time to Buy and Sell Stock with Cooldown, rebuilt from the original learning note

LeetCode note for Best Time to Buy and Sell Stock IV, rebuilt from the original learning note

LeetCode note for Best Time to Buy and Sell Stock III, rebuilt from the original learning note

LeetCode note for Best Time To Buy And Sell Stock II, rebuilt from the original learning note