DP as a State Machine

The Idea

Some DP has no table at all — just a handful of states and the moves between them. Here you are either holding a share or free of one. Each day, every state takes the better of staying put or arriving from the other state. Both are updated from yesterday's pair at once, which is why the assignment is simultaneous.

Real-World Example

A trading bot charged a flat fee per completed sale. It never enumerates trade sequences; it keeps two numbers overnight — the best balance while holding stock, and the best while in cash — and updates both against the next day's price.

The Code

prices = [7, 1, 5, 3, 6, 4]
fee = 2

hold, free = -prices[0], 0        # hold: own a share; free: own none
for p in prices[1:]:
    hold, free = max(hold, free - p), max(free, hold + p - fee)
    # buy today or keep holding   |   sell today or stay in cash

print(free)   # 3 — buy at 1, sell at 6, minus the fee

hold, free = -3, 0
for p in [3, 8]:
  hold, free = max(hold, free - p), max(free, hold + p - 1)
print(free)