Dynamic-Programming

LeetCode 32 note: a stack of indices whose bottom is the position just before the current valid run; the length is i - stack[-1]

LeetCode 834 note: rerooting DP: compute subtree sizes and ans[0] with root 0, then push ans[child] = ans[parent] - size + (n - size) to every node

LeetCode 2858 note: rerooting DP: count the reversals needed with root 0, then moving the root to a child adds 1 if that edge pointed down and subtracts 1 if it pointed up

LeetCode 968 note: post-order greedy with three states per node: has a camera, covered, not covered; place a camera only when a child is uncovered, and add one if the root is left uncovered

LeetCode 1372 note: each node returns two values, the longest zigzag starting left and starting right; going left extends the left child’s start-right value

LeetCode 124 note: DFS returns the best downward chain and updates the answer with left chain + node + right chain at every node; drop negative chains

LeetCode 1186 note: Kadane with one more state, ending here with no deletion or with one deletion; update the answer at every step

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

Interval DP (choose the last step / merge equal ends), partition DP into k segments, palindrome tables plus partitioning, and memoizing the whole state when it is too tangled to split

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

LeetCode 2267 note: the state is (r, c, open balance); the balance can be neither negative nor more than the remaining steps; search the states with BFS / DP and succeed at the end with balance 0

LeetCode 2218 note: piles are taken from the top, so taking x coins is worth a prefix sum; a grouped knapsack with dp[j] = the best value taking j coins so far, enumerating how many from each pile