DSA Notes

Dynamic Programming

Advanced DP I

Add a dimension for what the plain state forgets.

The idea

Sometimes the effect of taking an item depends on something besides the position: whether the number of items taken so far is even or odd, how many of a limited resource were used, which mode you are in.

Make that extra fact part of the state. f[i][s] is then the best result over the first i items while being in situation s, and each transition says how s changes.

The price is a table multiplied by the number of situations, so keep that number small.

Sample problem

1911. Maximum Alternating Subsequence Sum ↗ Medium

Choose a subsequence. Its alternating sum adds the 1st, 3rd, 5th… chosen numbers and subtracts the 2nd, 4th…. Return the largest alternating sum.

nums = [6,2,1,2,4,5]
output = 10   (6 − 1 + 5)

Why the solution works

Whether a number is added or subtracted depends on how many numbers were chosen before it. A state that only says “how far along the array” forgets that, so it cannot decide the sign.

Add what is missing as a second dimension: the parity of the count chosen so far. even is the best sum with an even count, odd with an odd count.

Each number x has three options: skip it; become the next odd pick (even + x); become the next even pick (odd − x). Both new values are computed from the old ones before either is overwritten.

Complexity: O(n) time, O(1) memory.

Watch out

  • Unreachable states must start at −INF (or +INF), not 0, or they leak into the answer.
  • Each extra dimension multiplies time and memory; check the total before coding.
  • When row i only reads row i−1, two rows are enough.
Watch it run

Practise on LeetCode