Dynamic Programming for Beginners: Climbing Stairs and Coin Change

Dynamic programming (DP) has a reputation for being hard, but the core idea is small: if a problem repeats the same sub-problems, solve each one once and remember the answer. This guide walks through the standard path from plain recursion to a table-based solution.

The recipe

1. Define what a sub-problem means in one sentence.
2. Write the recurrence: how a bigger answer is built from smaller ones.
3. Identify the base cases.
4. Add memoization (top-down) or fill a table (bottom-up).

Example 1: Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways are there to reach step n?

To stand on step i, you came from step i - 1 or step i - 2. So ways(i) = ways(i - 1) + ways(i - 2), with ways(0) = ways(1) = 1.

from functools import lru_cache

def climb_stairs(n):
    @lru_cache(None)
    def ways(i):
        if i <= 1:
            return 1
        return ways(i - 1) + ways(i - 2)
    return ways(n)

Without the cache, this recursion recomputes the same values and takes exponential time. With the cache each value is computed once, so the time is O(n).

We only ever need the last two values, so we can drop the table and keep O(1) space:

def climb_stairs_fast(n):
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Example 2: Coin Change

Given coin values and a target amount, find the fewest coins needed to make that amount, or -1 if it is impossible.

Let dp[a] be the minimum number of coins for amount a. For each coin c that fits, dp[a] = min(dp[a], dp[a - c] + 1). The base case is dp[0] = 0.

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Time is O(amount x number of coins) and space is O(amount). A greedy approach (always take the biggest coin) fails for inputs such as coins [1, 3, 4] and amount 6, where the best answer is 3 + 3, not 4 + 1 + 1. That is exactly why DP is needed.

How to practise

Start with Fibonacci-style problems (House Robber, Min Cost Climbing Stairs), then move to knapsack-style problems (Coin Change, Partition Equal Subset Sum), and finally grid and string problems (Unique Paths, Longest Common Subsequence). Always write the sub-problem definition before any code.