Overview

Dynamic programming applies when a problem breaks into overlapping subproblems — the same smaller question is asked again and again — and the best answer can be built from best answers to those subproblems. Instead of recomputing, you store each answer once. Climbing stairs, house robber and coin change are the classic first examples.

Every DP solution has the same four parts: a state (what dp[i] means, in words), a recurrence (how dp[i] is computed from smaller states), base cases, and an evaluation order. You can write it top-down as recursion with memoisation, or bottom-up as a loop filling a table. If dp[i] only depends on the last few values, you can keep just those and use O(1) space.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
GeneralO(number of states × work per state)
Climbing stairs / house robberO(n) time, O(1) space
Coin changeO(amount × coins)
LISO(n²) or O(n log n)

Patterns to recognise

Fibonacci-style

Use it for: Climbing stairs, house robber, decode ways.

dp[i] combines dp[i − 1] and dp[i − 2] depending on the choice at step i.

Unbounded choices

Use it for: Coin change, word break, perfect squares.

For each target value, try every option that fits and take the best.

Best ending here

Use it for: Longest increasing subsequence, maximum product subarray.

dp[i] = best answer for sequences ending exactly at index i.

Code template

House Robber (O(1) space) and Coin Change
def rob(nums):
    take = skip = 0                  # best if we rob / skip the previous house
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)


def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount        # dp[a] = fewest coins to make a
    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] <= amount else -1

Common mistakes

  • Starting to code before writing down what the state means.
  • Wrong base cases — dp[0] for "make amount 0" is 0 coins, not infinity.
  • Using INT_MAX as infinity and then adding 1 overflows.
  • Filling the table in an order where dp[i] is read before it is computed.

Quick check

Three questions on DP 1D. Get all three right to earn +15 XP.

  1. Dynamic programming applies when a problem has:

  2. Climbing stairs with 1 or 2 steps at a time: which recurrence counts the ways to reach step i?

  3. When dp[i] depends only on dp[i-1] and dp[i-2], the memory can be reduced from O(n) to:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on DP 1D?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor