From Recursion to DP

Dynamic programming (DP) is recursion that remembers. If a problem splits into smaller versions of itself, and those smaller versions repeat, you solve each one once, store the answer and reuse it.

How to spot a DP problem in an interview:

• "Count the ways" to do something
• "Minimum / maximum" cost, length, profit
• "Is it possible" to reach, split or build something
• You make a choice at every step (take or skip, step 1 or 2, which coin) and the best answer builds on best answers to smaller inputs
• A plain recursive solution would recompute the same subproblem again and again

Our running example is Climbing Stairs: you climb n steps, taking 1 or 2 at a time. How many different ways can you reach the top?

Think about your last move. To stand on step n you came from step n - 1 (a 1-step) or step n - 2 (a 2-step). So:

  ways(n) = ways(n - 1) + ways(n - 2)
  ways(0) = ways(1) = 1

That translates straight into recursion. But look at the call tree for ways(5):

                  ways(5)
             /             \\
        ways(4)           ways(3)
       /      \\          /      \\
   ways(3)   ways(2)  ways(2)  ways(1)
   /    \\     ...      ...
ways(2) ways(1)

ways(3) is computed twice, ways(2) three times. The tree roughly doubles every level: about O(2ⁿ) calls.

Step 1: memoize (top-down). Keep the recursion, but store every answer the first time you compute it. Python does this for you with @cache from functools: the decorator keeps a dictionary from arguments to results.

Now each ways(i) runs its body once, so there are only n + 1 distinct calls: O(n) time.

Step 2: tabulate (bottom-up). Memoization fills answers in whatever order the recursion asks for them. Tabulation fills them in a fixed order, smallest first, into a list dp. Every value a cell needs is already there when you get to it. No recursion, no depth limit.

Step 3: shrink the space. If a cell only looks back a fixed distance (here: two cells), you don't need the whole list. Keep two variables and slide them forward: O(n) time, O(1) space.

def ways(n):
    prev, cur = 1, 1        # ways(0), ways(1)
    for _ in range(n - 1):
        prev, cur = cur, prev + cur
    return cur

The DP recipe. Every DP solution in this unit answers the same four questions. Say them out loud in an interview before writing code:

1. State: what does dp[i] (or dp[i][j]) mean, in words? "Number of ways to reach step i."
2. Transition: how is a state built from smaller ones? "ways(i) = ways(i-1) + ways(i-2)."
3. Base case: which states do you know without recursion? "ways(0) = ways(1) = 1."
4. Answer: which state (or combination of states) is the final answer? "dp[n]."

Then pick an order that computes each state after the states it depends on, and check whether you can drop old rows to save space.