Tech World Software SchoolTWSS
0xB0Lesson 12 of 13

Reuse answers with dynamic programming

Break problems into overlapping subproblems and solve each once.

20 min 5-question quiz 1 code exercise
By the end of this lesson you can
  • 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

  1. Define the state: what does dp[i] mean? For example, “the fewest coins that make amount i.”
  2. Write the recurrence: how does dp[i] depend on smaller states? dp[i] = 1 + min(dp[i - coin]) over every coin.
  3. Set base cases: dp[0] = 0.
  4. Choose an order: fill the table so every state’s dependencies are ready (bottom-up), or recurse with a cache (top-down memoization).
solution.py
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))
Output
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.

Exercise 1

Make change with the fewest coins

+25 XP

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
main.py
Loading editor…

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…