Dynamic-Programming

Solving the Largest Rectangle in Histogram problem using monotonic stack approach

LeetCode 1696 note: dp[i] = nums[i] + max of the previous k dp values, with that max kept by a monotonic deque in O(n)

LeetCode 3638 note: greedily cut a segment as soon as a value below its maximum appears; until then the segment is non-decreasing, so its maximum is the previous value

Maximum subarray DP with an ending-here invariant

LeetCode 2745 note: AA and BB must alternate, using min(x, y) pairs plus one extra of the more common kind, and every AB fits in

LeetCode 473 note: the total must be divisible by 4; place sticks from longest to shortest into one of four sides, skipping a side that would overflow or that equals a side already tried

LeetCode 435 note: minimum removals = total minus the maximum kept; sort by right end and greedily keep the one ending earliest

LeetCode 397 note: even numbers are always halved; for odd numbers try +1 and -1 with memoized recursion, since n is too large for an n-sized array

LeetCode 396 note: F(k) and F(k - 1) differ by one formula: F(k) = F(k - 1) + sum - n × the element moved to the front

LeetCode 337 note: tree DP where each node returns the best (rob it, skip it) pair; not robbing alternate levels

LeetCode 313 note: generalizing LC 264 with one pointer per prime; with a heap, avoid pushing the same number many times

LeetCode 338 note: dp[i] = dp[i » 1] + (i & 1), or dp[i] = dp[i - highest power of two] + 1