Dynamic Programming • Pattern

DP on Stocks

Master the finite state machine approach to solve all variations of the "Best Time to Buy and Sell Stock" problems.

Overview

Stock problems involve a sequence of prices. At any day, you can choose to Buy, Sell, or Rest, subject to constraints (e.g. only hold 1 share at a time).

State Machine Modeling

We represent the states as `dp[day][holding_status]`. `holding_status` is typically 0 (no stock) or 1 (holding 1 share).

Transitions

From `0` to `1` costs `prices[i]`. From `1` to `0` adds `prices[i]`. Staying in the same state means doing nothing.

Space Optimization

Because the state on day `i` only depends on day `i-1`, we can optimize the O(N) space down to O(1) using a few variables.

State 0(Empty)

➡️

⬅️

State 1(Hold)

Code Tracker

:::

1// State Machine Transitions

2// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) // Sell or Rest

3// dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) // Buy or Rest

4

5let hold = -Infinity, empty = 0;

6for (let p of prices) {

7 let prevEmpty = empty;

8 empty = Math.max(empty, hold + p); // Sell

9 hold = Math.max(hold, prevEmpty - p); // Buy

10}

Dp On Stocks

Dp On Stocks

DP on Stocks

Overview

State Machine Modeling

Transitions

Space Optimization

DP on Stocks

Overview

State Machine Modeling

Transitions

Space Optimization