Dynamic Programming

Discrete Math · Axiom Academy

REAL WORLD Dynamic Programming: Stock Trading Optimization Learn how to optimize stock trading decisions using recurrence relations, state space, and memoization Imagine you're a trader who can see stock prices for the next week. Your goal is to maximize profit by buying and selling strategically. But there's a catch: after selling, you must wait one day before buying again (a "cooldown" period). You can buy and sell multiple times You can only hold one share at a time After selling, you must wait one day (cooldown) Let's visualize a week of stock prices: Question: What strategy would maximize your profit? In Dynamic Programming, we need to define our state space — all the possible situations we can be in at any point in time. Holding a stock — we bought earlier and are currently holding Not holding (can buy) — we can purchase a stock today Not holding (cooldown) — we just sold yesterday and must wait Let's define our state variables: Interactive Check: If you just sold a stock on Day 3, which state will you be in on Day 4? Deriving the Recurrence Relations Now comes the key insight: how does our profit at day i depend on previous days? To hold on day i : Either we already held yesterday, OR we buy today (can only buy if we're in rest state) To sell on day i : We must have been holding yesterday, and we sell today To rest on day i : Either we were resting yesterday, OR we were in cooldown from selling This gives us our recurrence relations:

This is the written version of the interactive lesson above. See the full Discrete Math course.