Dynamic Programming I: Foundations and One-Dimensional Problems

Dynamic programming (DP) has a reputation for being hard, and most of the difficulty comes from not having a method. DP is recursion plus memory: when a recursive solution solves the same subproblem many times, you store each answer the first time and reuse it. The method has four steps, and once you can run them, a large class of problems becomes routine. This chapter teaches the method on one-dimensional problems. The next chapter extends it to two dimensions.

1. When this pattern applies

Dynamic programming fits when:

• The problem asks for a count, a minimum or maximum, or whether something is possible (not for listing all solutions, which is backtracking).
• A solution can be built from solutions to smaller subproblems (optimal substructure).
• The same smaller subproblems recur (overlapping subproblems).
• Phrases like "how many ways", "minimum cost", "longest", "can we reach" appear.

A reliable test: write the naive recursion, and see whether the recursion tree contains repeated calls with the same arguments. If so, memoise.

2. The four-step method

1. Define the state. What does dp[i] (or f(i)) mean? Say it in one sentence, with units: "the minimum number of coins needed to make amount i". This sentence is the most important thing you write.
2. Write the transition. Express dp[i] in terms of smaller states. This is the recurrence.
3. Set the base cases. The smallest states whose answers are known directly.
4. Decide the order and the answer. Which states to compute first, and which state holds the final answer.

Then choose how to implement: top-down (recursion with a memo) or bottom-up (a table filled in order). Finally, see whether you can reduce the space.

3. A first example: Fibonacci, three ways

The naive recursion recomputes subproblems exponentially:

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

assert fib_naive(20) == 6765 and calls == 21891      # exponential growth in calls

Top-down (memoisation). Add a cache. Each state is computed once, so $O(n)$.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

assert fib_memo(50) == 12586269025

Bottom-up (tabulation). Fill the table from the base cases upward.

def fib_table(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

assert fib_table(50) == 12586269025

Space optimisation. dp[i] depends only on the previous two values, so keep two variables.

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

assert fib_constant_space(50) == 12586269025

This three-step progression, naive, memoised, tabulated, then space-optimised, is a good way to present any DP answer in an interview. It shows the reasoning and gives you checkpoints.

Top-down versus bottom-up. Top-down is easier to write (translate the recurrence directly) and computes only the needed states, at the cost of recursion overhead and a depth limit (Python's default is about 1,000, so deep recursions may need sys.setrecursionlimit or the bottom-up form). Bottom-up avoids recursion and makes space optimisation natural. Be comfortable with both.

4. Climbing stairs and the "number of ways" pattern

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

• State: dp[i] = number of ways to reach step i.
• Transition: you arrive from i - 1 or i - 2, so dp[i] = dp[i-1] + dp[i-2].
• Base: dp[0] = 1, dp[1] = 1.

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

assert climb_stairs(2) == 2
assert climb_stairs(5) == 8
assert climb_stairs(1) == 1

The structure, "ways to reach i is the sum of ways to reach each state you could come from", reappears in many problems. Decode ways counts the ways to decode a digit string as letters (1 to 26):

def num_decodings(s):
    if not s or s[0] == "0":
        return 0
    prev2, prev1 = 1, 1                      # ways for the empty prefix and the first character
    for i in range(1, len(s)):
        cur = 0
        if s[i] != "0":
            cur += prev1                     # decode s[i] on its own
        if 10 <= int(s[i - 1:i + 1]) <= 26:
            cur += prev2                     # decode the pair s[i-1:i+1]
        prev2, prev1 = prev1, cur
    return prev1

assert num_decodings("12") == 2
assert num_decodings("226") == 3
assert num_decodings("06") == 0
assert num_decodings("10") == 1

5. House robber: take or skip

Choose houses along a street to rob without robbing two adjacent ones, maximising money. At each house, either skip it (keep the best so far) or rob it (its value plus the best from two houses back).

• State: dp[i] = the maximum money from the first i houses.
• Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]).

def rob(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

assert rob([1, 2, 3, 1]) == 4
assert rob([2, 7, 9, 3, 1]) == 12
assert rob([]) == 0
assert rob([5]) == 5

House robber II (houses in a circle): the first and last are adjacent, so run the linear solution twice, once excluding the first house and once excluding the last, and take the larger.

def rob_circle(nums):
    if len(nums) == 1:
        return nums[0]
    return max(rob(nums[1:]), rob(nums[:-1]))

assert rob_circle([2, 3, 2]) == 3
assert rob_circle([1, 2, 3, 1]) == 4

The take-or-skip pattern is the heart of many problems: delete and earn, maximum sum of non-adjacent elements, and, with a second dimension, knapsack.

6. Maximum subarray (Kadane's algorithm)

The maximum sum of a contiguous subarray. At each position, either extend the best subarray ending at the previous position or start fresh at this element.

• State: best_ending_here = the maximum sum of a subarray that ends at the current index.
• Transition: best_ending_here = max(x, best_ending_here + x).

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray([1]) == 1
assert max_subarray([-3, -1, -2]) == -1

Note the distinction in the state: the DP value is "best sum ending at i", and the answer is the maximum over all i. Separating the DP state from the final answer is a recurring idea. Maximum product subarray tracks both the maximum and minimum ending here, because a negative number can flip the minimum into the maximum.

def max_product(nums):
    best = hi = lo = nums[0]
    for x in nums[1:]:
        candidates = (x, hi * x, lo * x)
        hi, lo = max(candidates), min(candidates)
        best = max(best, hi)
    return best

assert max_product([2, 3, -2, 4]) == 6
assert max_product([-2, 0, -1]) == 0
assert max_product([-2, 3, -4]) == 24

7. Coin change: unbounded choices

Given coin denominations, find the minimum number of coins to make an amount (each coin may be used any number of times), or -1 if impossible.

• State: dp[a] = the minimum number of coins to make amount a.
• Transition: dp[a] = 1 + min(dp[a - c]) over every coin c <= a.
• Base: dp[0] = 0. Unreached amounts are infinity.

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

assert coin_change([1, 2, 5], 11) == 3
assert coin_change([2], 3) == -1
assert coin_change([1], 0) == 0

Time $O(\text{amount}\times \text{coins})$, space $O(\text{amount})$. A greedy approach (always take the largest coin) fails for some coin sets, for example coins [1, 3, 4] and amount 6: greedy gives 4+1+1 (three coins), but 3+3 (two) is better. Mention this when explaining why DP is needed.

Coin change II counts the number of combinations. The loop order matters: iterating over coins in the outer loop counts combinations (order does not matter), and iterating over amounts in the outer loop would count permutations.

def coin_change_ways(amount, coins):
    dp = [1] + [0] * amount
    for c in coins:                              # coins outer: each combination counted once
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

assert coin_change_ways(5, [1, 2, 5]) == 4
assert coin_change_ways(3, [2]) == 0
assert coin_change_ways(0, [7]) == 1

8. Longest increasing subsequence

The longest strictly increasing subsequence (not necessarily contiguous).

$O(n^2)$ DP. dp[i] = the length of the longest increasing subsequence ending at index i. For each i, look at all earlier j with a smaller value.

def lis_quadratic(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

assert lis_quadratic([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert lis_quadratic([0, 1, 0, 3, 2, 3]) == 4
assert lis_quadratic([7, 7, 7]) == 1

$O(n\log n)$ with binary search. Maintain tails[k] = the smallest possible tail value of an increasing subsequence of length k + 1. For each number, binary search for where it fits, and replace that tail (or append if it is larger than all). The length of tails is the answer. (The list is not itself the subsequence, only its length is meaningful.)

import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)         # first tail >= x (strictly increasing)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

assert length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert length_of_lis([0, 1, 0, 3, 2, 3]) == 4
assert length_of_lis([7, 7, 7]) == 1
assert length_of_lis([]) == 0

Present the quadratic version first (it is easy to derive), and mention the logarithmic one as an optimisation.

9. Word break: DP over string positions

Can a string be segmented into words from a dictionary? dp[i] = whether the first i characters can be segmented. Position i is reachable if some earlier reachable j has s[j:i] in the dictionary.

def word_break(s, word_dict):
    words = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True                                  # the empty prefix
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

assert word_break("leetcode", ["leet", "code"]) is True
assert word_break("applepenapple", ["apple", "pen"]) is True
assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) is False

Time $O(n^2)$ substring checks (more precisely $O(n^2\cdot L)$ for slicing and hashing, where $L$ is the word length). You can bound the inner loop by the maximum word length. Compare with the backtracking version, which is exponential without memoisation: the DP table is exactly the memo.

10. Jump game: reachability

Can you reach the last index if nums[i] is the maximum jump length from i? The DP "reachable[i]" works in $O(n^2)$, and a greedy observation gives $O(n)$: track the furthest reachable index.

def can_jump(nums):
    furthest = 0
    for i, jump in enumerate(nums):
        if i > furthest:
            return False                          # we cannot even reach index i
        furthest = max(furthest, i + jump)
    return True

assert can_jump([2, 3, 1, 1, 4]) is True
assert can_jump([3, 2, 1, 0, 4]) is False
assert can_jump([0]) is True

This shows an important point for interviews: some DP problems have a greedy shortcut. Present the DP, then the greedy if you see it, and explain why it works.

11. Common mistakes

• Not defining the state in words. An unclear state leads to a wrong transition.
• Wrong base case, especially dp[0], which often means the empty input and is usually 1 for counting ways and 0 for minimising cost.
• Wrong iteration order, so a state is read before it is computed. Bottom-up must fill dependencies first.
• Initialising with 0 for a minimisation, so impossible states look free. Use infinity.
• Confusing combinations and permutations in counting problems. Loop order decides which you count.
• Off-by-one between dp indexes and string or array indexes. Write down what dp[i] covers.
• Using DP when a greedy or simpler formula exists, or using greedy when it is not correct.
• Forgetting that the answer is not always dp[n], as in Kadane (max over all states) and LIS.
• Exceeding the recursion limit in top-down on large inputs.

12. Practice set

1. Climbing stairs, min cost climbing stairs, tribonacci.
2. House robber I and II, delete and earn.
3. Maximum subarray, maximum product subarray, best time to buy and sell stock (with cooldown or fee).
4. Coin change I and II, perfect squares, minimum cost for tickets.
5. Longest increasing subsequence, number of longest increasing subsequences, Russian doll envelopes.
6. Word break I and II, decode ways.
7. Jump game I and II, partition equal subset sum (a 1D knapsack).
8. Longest palindromic substring (expand around centre, then DP).
9. Maximum length of a pair chain, wiggle subsequence.
10. Integer break, unique binary search trees (Catalan numbers).