# Best Time to Buy and Sell Stock

> LeetCode #121 — Best Time to Buy and Sell Stock. Solve on LeetCode, then implement here if you want it in your drill queue.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Canonical: https://learn.significanthobbies.com/curriculum/drills/lc-best-time-to-buy-and-sell-stock

LeetCode #121 — Best Time to Buy and Sell Stock. Solve on LeetCode, then implement here if you want it in your drill queue.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

## The mechanism

Dynamic programming is recursion with the repeated work cached. Define the state (what does dp[i] mean?), the recurrence (how does dp[i] build on earlier states?), and the base case. 1D DP means the state is a single index along a sequence.

## Expected evidence

Pass all LeetCode test cases for this problem.

## Hints

- Pattern hint: dp 1d.
- Start with brute force, then optimize time/space.
- Write down invariants before coding.

## Sources and practice

- [Dynamic programming (Wikipedia)](https://en.wikipedia.org/wiki/Dynamic_programming)
- [Algorithms (Erickson) — Ch. 3: Dynamic Programming](https://jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf)
- [MIT 6.006 L15 — Dynamic Programming Part 1 (SRTBOT, Fib, DAGs, Bowling)](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-15-dynamic-programming-part-1-srtbot-fib-dags-bowling/)
- [Longest increasing subsequence (cp-algorithms)](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html)
- [Study 1D DP](https://learn.significanthobbies.com/curriculum/concepts/dp-1d)
- [Try the interactive drill](https://learn.significanthobbies.com/drills/lc-best-time-to-buy-and-sell-stock)
- [All practice briefs](https://learn.significanthobbies.com/curriculum/drills/)