Reuse answers with dynamic programming
Break problems into overlapping subproblems and solve each once.
- Recognize overlapping subproblems.
- Write memoized (top-down) and tabulated (bottom-up) solutions.
- Define a DP state and recurrence.
Dynamic programming (DP) applies when a problem can be built from answers to smaller versions of itself, and those smaller versions repeat. Plain recursion recomputes them exponentially many times; DP stores each answer once. Typical signals: “how many ways”, “minimum cost”, “maximum value”, “is it possible” - over sequences, grids, or amounts.
Four steps to a DP solution
- Define the state: what does
dp[i]mean? For example, “the fewest coins that make amount i.” - Write the recurrence: how does
dp[i]depend on smaller states?dp[i] = 1 + min(dp[i - coin])over every coin. - Set base cases:
dp[0] = 0. - Choose an order: fill the table so every state’s dependencies are ready (bottom-up), or recurse with a cache (top-down memoization).
1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def ways_to_climb(n):
5 # ways to reach step n taking 1 or 2 steps at a time
6 if n <= 1:
7 return 1
8 return ways_to_climb(n - 1) + ways_to_climb(n - 2)
9
10print(ways_to_climb(5), ways_to_climb(30))8 1346269
Without the cache, ways_to_climb(30) makes over a million calls; with it, just 31. Bottom-up tabulation computes the same values in a loop and often lets you keep only the last few entries - here, two variables - for O(1) space. Always state the complexity as (number of states) × (work per state).
Key takeaways
DP = recursion + remembering answers to repeated subproblems.
Define state, recurrence, base cases, and evaluation order.
Complexity is roughly states × work per state.
Lesson quiz
5 questions · pass with 4 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: solve interview problems
Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.
Make change with the fewest coins
Read an amount, then a line of coin denominations. Print the fewest coins needed to make the amount exactly (unlimited coins of each kind), or -1 if it is impossible.
- Standard coins
- Greedy fails
- Impossible
- Zero amount
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…