Every code block has a Python and a C++ version; use the switch above a block to pick one. Your choice is remembered.

Introduction (Dynamic programming)

This course teaches dynamic programming, often shortened to DP, from the very first idea to some of the tricks used in contests. It assumes only that you can write a loop and a simple function. Nothing else is needed.

The course is a staircase. Chapter 1 is deliberately gentle: one small problem, one simple idea, no heavy math. Each chapter after it adds one new family of problems, and the math grows slowly. By the last chapters you will know how to speed up a slow DP and how to test your own solutions. If a later chapter looks hard, do not worry. Every chapter only uses what came before.

Every code example is shown in Python and in C++, so pick whichever language you like.

Chapter 1. What dynamic programming is

1.1 A recursion that is far too slow

Let's start with a simple sequence: Fibonacci numbers. The rule is easy: the first two numbers are 0 and 1, and every number after that is the sum of the two before it. So 0, 1, 1, 2, 3, 5, 8, 13, and so on. In math notation:

If we write this directly as a recursive function — a function that calls itself — it looks clean and short.

def fib_recursive(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib_recursive(n - 1) + fib_recursive(n - 2)


assert fib_recursive(0) == 0
assert fib_recursive(1) == 1
assert fib_recursive(6) == 8

int fib_recursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

But this clean code hides a problem. To compute fib_recursive(5), the function calls itself for 4 and 3. The call for 4 then calls 3 and 2. The call for 3 calls 2 and 1. Notice that fib_recursive(3) and fib_recursive(2) are computed multiple times. As n grows, the same subproblems — a subproblem is a smaller instance of the same question — are solved again and again. The call tree doubles in size roughly every step, so the running time is about $O(2^n)O(2^n)$. For n = 29 the program makes over one million calls. For n = 50 it would take hours.

1.2 Memoization (top-down)

The fix is simple: remember every answer the first time we compute it. This technique is called memoization — like writing notes on a memo pad so you don't redo work. We keep a table (an array or dictionary) where memo[k] stores f(k) once it is known. When the function is called, it checks the table first. If the value is there, it returns immediately. Otherwise it computes, saves, and returns.

def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


assert fib_memo(0) == 0
assert fib_memo(1) == 1
assert fib_memo(6) == 8
assert fib_memo(10) == 55

int fib_memo(int n, unordered_map<int, int>& memo) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;
    return memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
}

Now each value from 0 up to n is computed exactly once. The work per subproblem is $O(1)O(1)$, and there are $n+1n+1$ subproblems, so total time is $O(n)O(n)$. Space is also $O(n)O(n)$ for the table plus the recursion call stack. This style — starting from the target and recursing down to base cases — is called top-down dynamic programming.

1.3 Tables (bottom-up)

We can also fill the table in the opposite direction: start from the base cases and build up step by step to the answer we want. This is bottom-up dynamic programming. For Fibonacci we only need the two previous numbers, so we can even throw away older values and keep just two variables.

def fib_bottom_up(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


assert fib_bottom_up(0) == 0
assert fib_bottom_up(1) == 1
assert fib_bottom_up(6) == 8
assert fib_bottom_up(10) == 55

int fib_bottom_up(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Time is still $O(n)O(n)$, but space drops to $O(1)O(1)$ because we only store the last two numbers. Both top-down and bottom-up are dynamic programming; they just fill the table in different orders.

1.4 Three questions for every DP

When you see a new problem, ask these three questions to find the dynamic programming structure:

1. What is the state? A state is a compact description of a subproblem. For Fibonacci the state is just the integer n. For a problem on a string it might be an index i; for a grid it might be a cell (i, j). The set of all states must be finite and each state must correspond to a well-defined answer.
2. What is the transition? The transition tells how to compute the answer for one state using answers of smaller states. For Fibonacci the transition is f(n) = f(n-1) + f(n-2). A transition is simply a formula or rule that connects states.
3. Where do we start? These are the base cases — states whose answers are known without recursion. For Fibonacci the base cases are f(0) = 0 and f(1) = 1.

If you can answer these three questions clearly, you have a dynamic programming solution. The rest is just filling the table (bottom-up) or writing the memoized recursion (top-down).

1.5 Climbing stairs

This is exactly the problem Climbing Stairs. You stand at step 0 and want to reach step n. Each move you may climb 1 or 2 steps. How many distinct ways can you reach the top? Let ways[i] be the number of ways to reach step i. From step i-1 you can take a single step; from step i-2 you can take a double step. So ways[i] = ways[i-1] + ways[i-2]. The base cases: ways[0] = 1 (one way to stay at the ground), ways[1] = 1 (only a single step). This is the Fibonacci recurrence shifted by one.

Let's trace n = 4 by hand:

• ways[0] = 1
• ways[1] = 1
• ways[2] = 1 + 1 = 2
• ways[3] = 2 + 1 = 3
• ways[4] = 3 + 2 = 5

The five sequences for n=4 are: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2).

def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


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

int climb_stairs(int n) {
    if (n <= 1) return 1;
    int a = 1, b = 1;
    for (int i = 2; i <= n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Time $O(n)O(n)$, space $O(1)O(1)$.

Now a twist: Min Cost Climbing Stairs. Each step i has a non-negative cost cost[i]. You start at step 0 or step 1 (your choice) and want to reach the floor just past the last step (step n). When you land on a step you pay its cost. Find the minimum total cost. Let dp[i] be the minimum cost to reach step i. The transition: to stand on step i you must have come from i-1 or i-2, so dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Base cases: dp[0] = cost[0], dp[1] = cost[1]. The answer is min(dp[n-1], dp[n-2]) because you can finish from either of the last two steps.

Example: cost = [10, 15, 20].

• dp[0] = 10
• dp[1] = 15
• dp[2] = 20 + min(15, 10) = 30 Answer min(15, 30) = 15 (start at step 1, jump two steps to the floor).

def min_cost_climbing_stairs(cost: list[int]) -> int:
    n = len(cost)
    if n == 2:
        return min(cost[0], cost[1])
    dp0, dp1 = cost[0], cost[1]
    for i in range(2, n):
        dp0, dp1 = dp1, cost[i] + min(dp0, dp1)
    return min(dp0, dp1)


assert min_cost_climbing_stairs([10, 15, 20]) == 15
assert min_cost_climbing_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) == 6

int min_cost_climbing_stairs(vector<int>& cost) {
    int n = cost.size();
    if (n == 2) return min(cost[0], cost[1]);
    int dp0 = cost[0], dp1 = cost[1];
    for (int i = 2; i < n; ++i) {
        int dpi = cost[i] + min(dp0, dp1);
        dp0 = dp1;
        dp1 = dpi;
    }
    return min(dp0, dp1);
}

Time $O(n)O(n)$, space $O(1)O(1)$. Notice how the same three questions guided us: state is the step index, transition picks the cheaper previous step, base cases are the first two steps.

1.6 Check yourself

1. Why does the plain recursive Fibonacci function repeat work, and roughly how many calls does it make for input n?
2. What is the difference between top-down and bottom-up dynamic programming in terms of the order subproblems are solved?
3. For the climbing stairs problem, what are the state, the transition, and the base cases?
4. In min cost climbing stairs, why is the final answer min(dp[n-1], dp[n-2]) instead of dp[n]?

Chapter 2. Counting and choosing along a line

2.1 House robber

Imagine a row of houses, each with some cash inside. You want to take as much money as possible, but you cannot rob two houses that sit next to each other — the alarm would go off. This is exactly the problem House Robber.

Let's think about the last house in the row. You have two choices: rob it, or skip it. If you rob it, you cannot rob the previous house, so the best you can do is the money in this house plus the best amount from all houses before the previous one. If you skip it, the best amount is simply whatever you could get from all houses before this one.

We can write this idea as a recurrence. Let best[i] be the maximum money you can collect from the first i houses (using 1-based indexing for the houses, so house 1 is the first). Then:

The base cases are best[0] = 0 (no houses, no money) and best[1] = money[1] (only the first house). We fill the table from left to right. This bottom-up approach visits each house once, so the time cost is $O(n)O(n)$ and the space cost is $O(n)O(n)$, where $nn$ is the number of houses. We can even reduce space to $O(1)O(1)$ by keeping only the last two values.

Let's trace a tiny example by hand: money = [3, 2, 7, 10].

• best[0] = 0
• best[1] = 3
• best[2] = max(best[1], money[2] + best[0]) = max(3, 2 + 0) = 3
• best[3] = max(best[2], money[3] + best[1]) = max(3, 7 + 3) = 10
• best[4] = max(best[3], money[4] + best[2]) = max(10, 10 + 3) = 13

The answer is 13 (rob houses 1 and 4).

def house_robber(money: list[int]) -> int:
    """Return the maximum amount that can be robbed without adjacent houses."""
    n = len(money)
    if n == 0:
        return 0
    if n == 1:
        return money[0]
    # dp[i] = best for first i houses (1-based)
    dp = [0] * (n + 1)
    dp[1] = money[0]
    for i in range(2, n + 1):
        dp[i] = max(dp[i - 1], money[i - 1] + dp[i - 2])
    return dp[n]

# Quick checks
assert house_robber([3, 2, 7, 10]) == 13
assert house_robber([3, 2, 5, 10, 7]) == 15  # 3 + 5 + 7
assert house_robber([]) == 0
assert house_robber([5]) == 5

int houseRobber(const vector<int>& money) {
    int n = money.size();
    if (n == 0) return 0;
    if (n == 1) return money[0];
    vector<int> dp(n + 1);
    dp[1] = money[0];
    for (int i = 2; i <= n; ++i) {
        dp[i] = max(dp[i - 1], money[i - 1] + dp[i - 2]);
    }
    return dp[n];
}

2.2 House robber on a circle

Now suppose the houses form a circle — the first and last houses are also neighbors. This is exactly the problem House Robber II. You cannot simply run the same linear algorithm because the first and last houses are now adjacent.

The trick is to break the circle into two linear cases: either you rob the first house (and therefore cannot rob the last), or you skip the first house (and the last house is free to choose). Compute the best for each case using the linear algorithm from before, then take the larger of the two.

If there is only one house, the answer is just that house's money. For two houses, the answer is the maximum of the two. For three or more, we run the linear solver on money[0..n-2] (exclude last) and on money[1..n-1] (exclude first). The time cost is still $O(n)O(n)$ and space is $O(n)O(n)$ (or $O(1)O(1)$ with the optimized version).

Example: money = [2, 3, 2]. Case A (rob first, exclude last): houses [2, 3] → best is 3. Case B (exclude first): houses [3, 2] → best is 3. Answer is 3.

def house_robber_linear(money: list[int]) -> int:
    """Helper for the linear version (same as before)."""
    n = len(money)
    if n == 0:
        return 0
    if n == 1:
        return money[0]
    dp = [0] * (n + 1)
    dp[1] = money[0]
    for i in range(2, n + 1):
        dp[i] = max(dp[i - 1], money[i - 1] + dp[i - 2])
    return dp[n]

def house_robber_ii(money: list[int]) -> int:
    """Circular version: first and last are adjacent."""
    n = len(money)
    if n == 0:
        return 0
    if n == 1:
        return money[0]
    if n == 2:
        return max(money[0], money[1])
    # Case 1: rob first, skip last
    case1 = house_robber_linear(money[:-1])
    # Case 2: skip first, last is available
    case2 = house_robber_linear(money[1:])
    return max(case1, case2)

assert house_robber_ii([2, 3, 2]) == 3
assert house_robber_ii([1, 2, 3, 1]) == 4  # 1 + 3
assert house_robber_ii([1, 2, 3]) == 3
assert house_robber_ii([5]) == 5

int houseRobberLinear(const vector<int>& money) {
    int n = money.size();
    if (n == 0) return 0;
    if (n == 1) return money[0];
    vector<int> dp(n + 1);
    dp[1] = money[0];
    for (int i = 2; i <= n; ++i) {
        dp[i] = max(dp[i - 1], money[i - 1] + dp[i - 2]);
    }
    return dp[n];
}

int houseRobberII(const vector<int>& money) {
    int n = money.size();
    if (n == 0) return 0;
    if (n == 1) return money[0];
    if (n == 2) return max(money[0], money[1]);
    vector<int> first(money.begin(), money.end() - 1);
    vector<int> second(money.begin() + 1, money.end());
    return max(houseRobberLinear(first), houseRobberLinear(second));
}

2.3 Decode ways

A message containing digits can be decoded into letters where '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'. Given a string of digits, count how many ways it can be decoded. This is exactly the problem Decode Ways.

Let ways[i] be the number of decodings for the prefix of length i (first i characters). Look at the last one or two digits of that prefix. If the last digit is not '0', it can stand alone as a letter, so we add ways[i-1]. If the last two digits form a number between 10 and 26 inclusive, they can be decoded together as one letter, so we add ways[i-2]. Base case: ways[0] = 1 (empty string has one decoding — do nothing).

Example: s = "12". ways[0] = 1. ways[1]: last digit '2' is valid → ways[0] = 1. ways[2]: last digit '2' valid → add ways[1] = 1; last two digits "12" valid → add ways[0] = 1. Total ways[2] = 2 (decodings: "AB" and "L").

Time cost is $O(n)O(n)$, space is $O(n)O(n)$ (reducible to $O(1)O(1)$).

def num_decodings(s: str) -> int:
    """Return the number of ways to decode the digit string s."""
    n = len(s)
    if n == 0:
        return 0
    dp = [0] * (n + 1)
    dp[0] = 1
    # first character
    dp[1] = 0 if s[0] == '0' else 1
    for i in range(2, n + 1):
        # single digit
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        # two digits
        two = int(s[i - 2:i])
        if 10 <= two <= 26:
            dp[i] += dp[i - 2]
    return dp[n]

assert num_decodings("12") == 2
assert num_decodings("226") == 3  # BBF, BZ, VF
assert num_decodings("06") == 0
assert num_decodings("10") == 1
assert num_decodings("") == 0

int numDecodings(const string& s) {
    int n = s.size();
    if (n == 0) return 0;
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = (s[0] == '0') ? 0 : 1;
    for (int i = 2; i <= n; ++i) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1];
        int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (10 <= two && two <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

2.4 Coin change

You have coins of different denominations and want to make a target amount. Two classic questions: what is the fewest coins needed (problem Coin Change), and how many different combinations of coins make the amount (problem Coin Change II). The loop order in the inner loop changes the meaning of the answer.

Fewest coins

Let dp[x] be the minimum coins to make amount x. Initialize dp[0] = 0 and all others to a large number (infinity). For each coin c, we try to improve every amount x from c up to target: dp[x] = min(dp[x], dp[x - c] + 1). The outer loop goes over coins, the inner loop goes over amounts increasing. This allows using the same coin many times. At the end, if dp[target] is still infinity, the amount cannot be made.

Example: coins = [1, 3, 4], target = 6. Table after all coins:

• dp[0]=0
• dp[1]=1 (1)
• dp[2]=2 (1+1)
• dp[3]=1 (3)
• dp[4]=1 (4)
• dp[5]=2 (4+1)
• dp[6]=2 (3+3)

Time cost is $O(n\cdot \text{target})O(n\; \backslash cdot\; \backslash text\{target\})$, space is $O(\text{target})O(\backslash text\{target\})$.

Number of combinations (order of coins does not matter)

Now let ways[x] be the number of combinations to make amount x. Initialize ways[0] = 1. For each coin c, for x from c to target: ways[x] += ways[x - c]. The outer loop over coins and inner loop increasing over amounts ensures each combination is counted once regardless of coin order. If we swapped the loops (amounts outer, coins inner), we would count permutations instead of combinations.

Example: coins = [1, 2], target = 3. Combinations: 1+1+1, 1+2 → 2 ways. With loops swapped we would get 1+1+1, 1+2, 2+1 → 3 ways.

def coin_change_min(coins: list[int], target: int) -> int:
    """Fewest coins to make target, or -1 if impossible."""
    INF = target + 1
    dp = [INF] * (target + 1)
    dp[0] = 0
    for c in coins:
        for x in range(c, target + 1):
            dp[x] = min(dp[x], dp[x - c] + 1)
    return -1 if dp[target] == INF else dp[target]

def coin_change_ways(coins: list[int], target: int) -> int:
    """Number of combinations to make target (order of coins ignored)."""
    dp = [0] * (target + 1)
    dp[0] = 1
    for c in coins:
        for x in range(c, target + 1):
            dp[x] += dp[x - c]
    return dp[target]

assert coin_change_min([1, 3, 4], 6) == 2
assert coin_change_min([2], 3) == -1
assert coin_change_ways([1, 2], 3) == 2
assert coin_change_ways([2, 5], 3) == 0

int coinChangeMin(const vector<int>& coins, int target) {
    const int INF = target + 1;
    vector<int> dp(target + 1, INF);
    dp[0] = 0;
    for (int c : coins) {
        for (int x = c; x <= target; ++x) {
            dp[x] = min(dp[x], dp[x - c] + 1);
        }
    }
    return dp[target] == INF ? -1 : dp[target];
}

int coinChangeWays(const vector<int>& coins, int target) {
    vector<int> dp(target + 1);
    dp[0] = 1;
    for (int c : coins) {
        for (int x = c; x <= target; ++x) {
            dp[x] += dp[x - c];
        }
    }
    return dp[target];
}

2.5 Perfect squares and word break

Some problems ask whether a thing can be split into valid pieces, or what is the minimum number of pieces. The idea is the same: try every possible last piece.

Perfect squares

Given an integer n, find the least number of perfect square numbers (1, 4, 9, 16, ...) that sum to n. This is exactly the problem Perfect Squares. Let dp[x] be the minimum squares for x. For each x from 1 to n, try every square s = k*k <= x and take dp[x] = min(dp[x], dp[x - s] + 1). Base dp[0] = 0.

Example: n = 12. Squares ≤ 12: 1, 4, 9.

• dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=1, dp[5]=2, dp[6]=3, dp[7]=4, dp[8]=2 (4+4), dp[9]=1, dp[10]=2 (9+1), dp[11]=3, dp[12]=3 (4+4+4).

Time cost is $O(n\sqrt{n})O(n\; \backslash sqrt\{n\})$, space is $O(n)O(n)$.

Word break

Given a string s and a list of words dict, decide if s can be segmented into a sequence of dictionary words. This is exactly the problem Word Break. Let can[i] be true if the prefix of length i can be segmented. can[0] = true. For each i from 1 to n, check every j < i: if can[j] is true and s[j:i] is in the dictionary, set can[i] = true.

Example: s = "leetcode", dict = ["leet", "code"].

• can[0]=true
• i=4: j=0, can[0]=true, s[0:4]="leet" in dict → can[4]=true
• i=8: j=4, can[4]=true, s[4:8]="code" in dict → can[8]=true

Time cost is $O(n^2)O(n^2)$ for the nested loops (substring lookup is $O(1)O(1)$ with a hash set), space is $O(n)O(n)$.

def num_squares(n: int) -> int:
    """Least number of perfect squares that sum to n."""
    dp = [n] * (n + 1)  # worst case: n = 1+1+...
    dp[0] = 0
    for x in range(1, n + 1):
        k = 1
        while k * k <= x:
            s = k * k
            dp[x] = min(dp[x], dp[x - s] + 1)
            k += 1
    return dp[n]

def word_break(s: str, word_dict: list[str]) -> bool:
    """Return True if s can be segmented into words from word_dict."""
    word_set = set(word_dict)
    n = len(s)
    can = [False] * (n + 1)
    can[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if can[j] and s[j:i] in word_set:
                can[i] = True
                break
    return can[n]

assert num_squares(12) == 3
assert num_squares(13) == 2  # 9 + 4
assert word_break("leetcode", ["leet", "code"]) == True
assert word_break("applepenapple", ["apple", "pen"]) == True
assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) == False

int numSquares(int n) {
    vector<int> dp(n + 1, n);
    dp[0] = 0;
    for (int x = 1; x <= n; ++x) {
        for (int k = 1; k * k <= x; ++k) {
            dp[x] = min(dp[x], dp[x - k * k] + 1);
        }
    }
    return dp[n];
}

bool wordBreak(const string& s, const vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> can(n + 1);
    can[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (can[j] && dict.count(s.substr(j, i - j))) {
                can[i] = true;
                break;
            }
        }
    }
    return can[n];
}

2.6 Dice roll sum

You have d dice, each with f faces numbered 1 to f. How many ways can the dice sum to a target t? This is exactly the problem Dice Roll Sum.

Let dp[i][s] be the number of ways to get sum s using the first i dice. Base: dp[0][0] = 1. For each die i from 1 to d, for each possible sum s from i to i*f, we add the ways from the previous die with each face value: dp[i][s] = sum(dp[i-1][s - face] for face in 1..f if s - face >= 0).

We can compress this to a 1D array by iterating sums backwards (from high to low) for each die, or we can keep a 2D table for clarity. The 2D version uses $O(d\cdot t)O(d\; \backslash cdot\; t)$ time and space. The 1D version uses $O(t)O(t)$ space.

Example: d = 2, f = 6, t = 7. Ways: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1) → 6 ways.

def dice_roll_sum(d: int, f: int, target: int) -> int:
    """Number of ways to roll d f-faced dice to get sum target."""
    dp = [0] * (target + 1)
    dp[0] = 1
    for _ in range(d):
        new_dp = [0] * (target + 1)
        for s in range(1, target + 1):
            for face in range(1, f + 1):
                if s - face >= 0:
                    new_dp[s] += dp[s - face]
        dp = new_dp
    return dp[target]

assert dice_roll_sum(2, 6, 7) == 6
assert dice_roll_sum(1, 6, 3) == 1
assert dice_roll_sum(2, 6, 12) == 1  # 6+6
assert dice_roll_sum(3, 6, 7) == 15

int diceRollSum(int d, int f, int target) {
    vector<int> dp(target + 1);
    dp[0] = 1;
    for (int i = 0; i < d; ++i) {
        vector<int> ndp(target + 1);
        for (int s = 1; s <= target; ++s) {
            for (int face = 1; face <= f; ++face) {
                if (s - face >= 0) ndp[s] += dp[s - face];
            }
        }
        dp.swap(ndp);
    }
    return dp[target];
}

2.7 Check yourself

1. In the house robber recurrence, why do we use best[i-2] when we choose to rob house i?
2. For coin change (fewest coins), what happens if the inner loop goes over amounts in decreasing order instead of increasing?
3. In word break, why do we check can[j] before looking up s[j:i] in the dictionary?
4. For dice roll sum with 2 dice and 6 faces, how many ways are there to get a sum of 2, and how many for a sum of 7?

Chapter 3. Dynamic programming on grids

3.1 Counting paths in a grid

Imagine a robot sitting in the top-left corner of a rectangular board. The robot can only move right or down, one cell at a time. We want to know how many different ways the robot can reach the bottom-right corner. This is exactly the problem Unique Paths.

Let the board have $mm$ rows and $nn$ columns. Number the rows $00$ to $m-1m-1$ from top to bottom, and columns $00$ to $n-1n-1$ from left to right. The robot starts at $(0,0)(0,0)$ and must finish at $(m-1,n-1)(m-1,n-1)$.

If we write the number of ways to reach each cell in a table, a simple pattern appears. The first row and the first column can only be reached in one way: by moving straight right or straight down. For any other cell $(i,j)(i,j)$, the robot must have come from the cell above $(i-1,j)(i-1,j)$ or from the cell to the left $(i,j-1)(i,j-1)$. So the number of ways to reach $(i,j)(i,j)$ is the sum of the ways to reach those two neighbours.

Let us work through a $3\times 33\; \backslash times\; 3$ board by hand. The table of ways looks like this:

The answer is $66$. Notice how we filled the table row by row, left to right. We always used values that were already computed. This order works because every cell depends only on its top and left neighbours, which live in earlier rows or earlier columns.

The algorithm runs in $O(mn)O(mn)$ time and uses $O(mn)O(mn)$ space if we keep the whole table. We can reduce space to $O(n)O(n)$ by keeping only the current row, because each new cell only needs the value to its left (already in the current row) and the value above (stored in the same column from the previous row).

def unique_paths(m: int, n: int) -> int:
    dp = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[-1]

assert unique_paths(3, 3) == 6
assert unique_paths(2, 2) == 2

int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

3.2 Blocked cells and cheapest paths

Now suppose some cells are blocked and the robot cannot step on them. This is the problem Unique Paths with Obstacles. We use the same table idea, but a blocked cell gets a value of $00$ ways. The start cell is $11$ if it is free, otherwise $00$. Every other free cell adds the ways from top and left, treating blocked neighbours as $00$.

Next, imagine each cell has a cost (a non-negative number) and we want the cheapest total cost from start to finish. This is Minimum Path Sum. The recurrence changes from counting to minimizing: the cheapest cost to reach $(i,j)(i,j)$ is the cell's own cost plus the smaller of the cheapest costs to reach $(i-1,j)(i-1,j)$ and $(i,j-1)(i,j-1)$. The first row and first column are just cumulative sums because there is only one way to reach them.

Let us trace a tiny $2\times 32\; \backslash times\; 3$ grid with costs:

1 2 3
4 5 6

The table of minimum costs:

The answer is $1212$. We fill the table in the same top-left to bottom-right order. Time $O(mn)O(mn)$, space $O(n)O(n)$ with a rolling row.

def min_path_sum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]
    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
    return dp[-1]

assert min_path_sum([[1,2,3],[4,5,6]]) == 12
assert min_path_sum([[1]]) == 1

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n, INT_MAX);
    dp[0] = grid[0][0];
    for (int j = 1; j < n; ++j) dp[j] = dp[j - 1] + grid[0][j];
    for (int i = 1; i < m; ++i) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; ++j) {
            dp[j] = grid[i][j] + min(dp[j], dp[j - 1]);
        }
    }
    return dp[n - 1];
}

For Unique Paths with Obstacles we only need to zero out blocked cells:

def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = 1 if grid[0][0] == 0 else 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j - 1]
    return dp[-1]

assert unique_paths_with_obstacles([[0,0,0],[0,1,0],[0,0,0]]) == 2
assert unique_paths_with_obstacles([[1]]) == 0

int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n, 0);
    dp[0] = grid[0][0] == 0 ? 1 : 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) dp[j] = 0;
            else if (j > 0) dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

3.3 Triangles and falling paths

A triangle of numbers looks like this:

   2
  3 4
 6 5 7
4 1 8 3

We start at the top and move down to adjacent numbers on the next row. The goal is to find the path with the smallest sum. This is Triangle Minimum Path. The triangle has $nn$ rows. Row $ii$ has $i+1i+1$ numbers, indexed $00$ to $ii$. From position $(i,j)(i,j)$ we can go to $(i+1,j)(i+1,j)$ or $(i+1,j+1)(i+1,j+1)$.

It is natural to fill a DP table from the bottom up. The bottom row's best sums are just the numbers themselves. For each cell above, its best sum is its own value plus the smaller of the two cells directly below it. Working upward, the top cell finally holds the answer.

Let us compute the example by hand. Bottom row: $4,1,8,34,\; 1,\; 8,\; 3$. Row above: $6+\min (4,1)=76+\backslash min(4,1)=7$, $5+\min (1,8)=65+\backslash min(1,8)=6$, $7+\min (8,3)=107+\backslash min(8,3)=10$. Next: $3+\min (7,6)=93+\backslash min(7,6)=9$, $4+\min (6,10)=104+\backslash min(6,10)=10$. Top: $2+\min (9,10)=112+\backslash min(9,10)=11$. The answer is $1111$.

We can do this in place on a copy of the last row, updating from left to right: the new value at position $jj$ needs the old values at positions $jj$ and $j+1j+1$, and position $j+1j+1$ has not been changed yet. Time $O(n^2)O(n^2)$, space $O(n)O(n)$.

def minimum_total(triangle: list[list[int]]) -> int:
    dp = triangle[-1][:]
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(i + 1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

assert minimum_total([[2],[3,4],[6,5,7],[4,1,8,3]]) == 11
assert minimum_total([[-10]]) == -10

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<int> dp = triangle.back();
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
        }
    }
    return dp[0];
}

A close cousin is Minimum Falling Path Sum. Here we have a square $n\times nn\; \backslash times\; n$ matrix. We start at any cell in the top row and move down to the next row, choosing the same column or one step left or right. We want the smallest sum reaching the bottom row. The recurrence is similar: $dp[i][j]=grid[i][j]+\min (dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])dp[i][j]\; =\; grid[i][j]\; +\; \backslash min(dp[i-1][j-1],\; dp[i-1][j],\; dp[i-1][j+1])$ with boundary checks. We fill top to bottom. Time $O(n^2)O(n^2)$, space $O(n)O(n)$ with two rows.

def min_falling_path_sum(grid: list[list[int]]) -> int:
    n = len(grid)
    prev = grid[0][:]
    for i in range(1, n):
        cur = [0] * n
        for j in range(n):
            best = prev[j]
            if j > 0: best = min(best, prev[j - 1])
            if j + 1 < n: best = min(best, prev[j + 1])
            cur[j] = grid[i][j] + best
        prev = cur
    return min(prev)

assert min_falling_path_sum([[2,1,3],[6,5,4],[7,8,9]]) == 13
assert min_falling_path_sum([[-19,57],[-40,-5]]) == -59

int minFallingPathSum(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<int> prev = grid[0];
    for (int i = 1; i < n; ++i) {
        vector<int> cur(n);
        for (int j = 0; j < n; ++j) {
            int best = prev[j];
            if (j > 0) best = min(best, prev[j - 1]);
            if (j + 1 < n) best = min(best, prev[j + 1]);
            cur[j] = grid[i][j] + best;
        }
        prev = move(cur);
    }
    return *min_element(prev.begin(), prev.end());
}

3.4 Squares inside a grid

Two problems ask about squares made of $11$s in a binary matrix. Maximal Square wants the area of the largest all-$11$ square. Count Square Submatrices wants the total number of square submatrices that are all $11$s.

Let $dp[i][j]dp[i][j]$ be the side length of the largest all-$11$ square whose bottom-right corner is at $(i,j)(i,j)$. If $grid[i][j]=0grid[i][j]\; =\; 0$, then $dp[i][j]=0dp[i][j]\; =\; 0$. Otherwise, the square can extend only as far as the smallest of its three neighbours: top, left, and top-left. So $dp[i][j]=1+\min (dp[i-1][j],dp[i][j-1],dp[i-1][j-1])dp[i][j]\; =\; 1\; +\; \backslash min(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1])$.

Why does this work? A square of side $kk$ ending at $(i,j)(i,j)$ needs a square of side $k-1k-1$ ending at each of those three neighbours. The smallest neighbour limits how large we can go.

For a $3\times 33\; \backslash times\; 3$ all-$11$ matrix, the $dpdp$ table becomes:

The maximal square has side $33$, area $99$. The sum of all entries is $1+1+1+1+2+2+1+2+3=141+1+1+1+2+2+1+2+3\; =\; 14$, which is exactly the count of all square submatrices (each cell contributes the number of squares ending there).

We can compute row by row with a single array of length $nn$, keeping the previous row's values in a variable for the top-left neighbour. Time $O(mn)O(mn)$, space $O(n)O(n)$.

def maximal_square(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [0] * (n + 1)
    max_side = 0
    prev = 0
    for i in range(m):
        for j in range(n):
            temp = dp[j + 1]
            if grid[i][j] == 1:
                dp[j + 1] = 1 + min(dp[j], dp[j + 1], prev)
                max_side = max(max_side, dp[j + 1])
            else:
                dp[j + 1] = 0
            prev = temp
        prev = 0
    return max_side * max_side

def count_squares(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [0] * (n + 1)
    total = 0
    prev = 0
    for i in range(m):
        for j in range(n):
            temp = dp[j + 1]
            if grid[i][j] == 1:
                dp[j + 1] = 1 + min(dp[j], dp[j + 1], prev)
                total += dp[j + 1]
            else:
                dp[j + 1] = 0
            prev = temp
        prev = 0
    return total

assert maximal_square([[1,1,1],[1,1,1],[1,1,1]]) == 9
assert count_squares([[1,1,1],[1,1,1],[1,1,1]]) == 14
assert maximal_square([[0]]) == 0

int maximalSquare(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n + 1, 0);
    int maxSide = 0, prev = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int temp = dp[j + 1];
            if (grid[i][j] == 1) {
                dp[j + 1] = 1 + min({dp[j], dp[j + 1], prev});
                maxSide = max(maxSide, dp[j + 1]);
            } else {
                dp[j + 1] = 0;
            }
            prev = temp;
        }
        prev = 0;
    }
    return maxSide * maxSide;
}

int countSquares(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n + 1, 0);
    int total = 0, prev = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int temp = dp[j + 1];
            if (grid[i][j] == 1) {
                dp[j + 1] = 1 + min({dp[j], dp[j + 1], prev});
                total += dp[j + 1];
            } else {
                dp[j + 1] = 0;
            }
            prev = temp;
        }
        prev = 0;
    }
    return total;
}

3.5 Filling the table backwards: dungeon game

In Dungeon Game a knight starts at the top-left of a grid and must reach the bottom-right. Each cell changes the knight's health (positive heals, negative damages). The knight can only move right or down. We need the minimum initial health so the knight never drops to $00$ or below.

If we try to go forward, we don't know how much health we will need later. The trick is to go backward from the destination. Let $dp[i][j]dp[i][j]$ be the minimum health needed to enter cell $(i,j)(i,j)$ and survive to the end. At the bottom-right, we need at least $11$ health after the cell's effect, so $dp[m-1][n-1]=\max (1,1-grid[m-1][n-1])dp[m-1][n-1]\; =\; \backslash max(1,\; 1\; -\; grid[m-1][n-1])$.

For other cells, the knight will choose the easier of the two next steps (right or down). If we go right, we need $dp[i][j+1]dp[i][j+1]$ health entering the next cell. So we need $dp[i][j+1]-grid[i][j]dp[i][j+1]\; -\; grid[i][j]$ health entering the current cell. But health can never be less than $11$. So $dp[i][j]=\max (1,\min (dp[i+1][j],dp[i][j+1])-grid[i][j])dp[i][j]\; =\; \backslash max(1,\; \backslash min(dp[i+1][j],\; dp[i][j+1])\; -\; grid[i][j])$.

We fill the table from bottom-right to top-left. Time $O(mn)O(mn)$, space $O(n)O(n)$ with a rolling row from right to left.

Let us trace a tiny $2\times 22\; \backslash times\; 2$ grid:

-2  -3
-5 -10

Destination $(1,1)(1,1)$: need $\max (1,1-(-10))=11\backslash max(1,\; 1\; -\; (-10))\; =\; 11$. $(1,0)(1,0)$: only right, need $\max (1,11-(-5))=16\backslash max(1,\; 11\; -\; (-5))\; =\; 16$. $(0,1)(0,1)$: only down, need $\max (1,11-(-3))=14\backslash max(1,\; 11\; -\; (-3))\; =\; 14$. $(0,0)(0,0)$: choose min of right ($1414$) and down ($1616$), so $\max (1,14-(-2))=16\backslash max(1,\; 14\; -\; (-2))\; =\; 16$.

Answer is $1616$.

def calculate_minimum_hp(dungeon: list[list[int]]) -> int:
    m, n = len(dungeon), len(dungeon[0])
    dp = [float('inf')] * (n + 1)
    dp[n - 1] = 1
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            need = min(dp[j], dp[j + 1]) - dungeon[i][j]
            dp[j] = max(1, need)
    return dp[0]

assert calculate_minimum_hp([[-2,-3],[-5,-10]]) == 16
assert calculate_minimum_hp([[0]]) == 1
assert calculate_minimum_hp([[100]]) == 1

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    vector<int> dp(n + 1, INT_MAX);
    dp[n - 1] = 1;
    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            int need = min(dp[j], dp[j + 1]) - dungeon[i][j];
            dp[j] = max(1, need);
        }
    }
    return dp[0];
}

3.6 The largest all-zero rectangle

Now we look for the largest rectangle containing only zeros in a binary matrix. This is sometimes called the maximal rectangle of zeros. We can solve it in $O(mn)O(mn)$ time using a stack, similar to the largest rectangle in a histogram.

First, for each cell we compute how many consecutive zeros are directly above it (including itself). Call this $height[i][j]height[i][j]$. If $grid[i][j]=1grid[i][j]\; =\; 1$, then $height[i][j]=0height[i][j]\; =\; 0$. Otherwise $height[i][j]=1+height[i-1][j]height[i][j]\; =\; 1\; +\; height[i-1][j]$. This turns each row into a histogram where the bar heights are the number of continuous zeros upward.

For a fixed row, we want the largest rectangle in this histogram. The classic stack algorithm finds it in $O(n)O(n)$: scan left to right, maintain a stack of column indices with increasing heights. When the current height is lower than the stack top, we pop and compute the area of the rectangle that uses the popped height as the limiting bar. The width extends from the new stack top (or left border) to the current column minus one.

We do this for every row and keep the maximum area. Total time $O(mn)O(mn)$, space $O(n)O(n)$.

Let us trace a small example:

0 0 1
0 0 0
1 0 0

Heights row by row: Row 0: $1,1,01,\; 1,\; 0$ Row 1: $2,2,12,\; 2,\; 1$ Row 2: $0,3,20,\; 3,\; 2$

For row 1 histogram $[2,2,1][2,2,1]$, the largest rectangle has area $44$ (columns $00$ and $11$, height $22$). For row 2 histogram $[0,3,2][0,3,2]$, the largest is $44$ (columns $11$ and $22$, height $22$). Overall answer $44$.

def maximal_rectangle_of_zeros(grid: list[list[int]]) -> int:
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    height = [0] * n
    best = 0
    for i in range(m):
        for j in range(n):
            height[j] = height[j] + 1 if grid[i][j] == 0 else 0
        stack = []
        for j in range(n + 1):
            cur_h = height[j] if j < n else 0
            while stack and cur_h < height[stack[-1]]:
                h = height[stack.pop()]
                left = stack[-1] if stack else -1
                area = h * (j - left - 1)
                best = max(best, area)
            stack.append(j)
    return best

assert maximal_rectangle_of_zeros([[0,0,1],[0,0,0],[1,0,0]]) == 4
assert maximal_rectangle_of_zeros([[1,1],[1,1]]) == 0
assert maximal_rectangle_of_zeros([[0]]) == 1

int maximalRectangleOfZeros(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    vector<int> height(n, 0);
    int best = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            height[j] = grid[i][j] == 0 ? height[j] + 1 : 0;
        }
        vector<int> st;
        for (int j = 0; j <= n; ++j) {
            int cur = (j < n) ? height[j] : 0;
            while (!st.empty() && cur < height[st.back()]) {
                int h = height[st.back()];
                st.pop_back();
                int left = st.empty() ? -1 : st.back();
                best = max(best, h * (j - left - 1));
            }
            st.push_back(j);
        }
    }
    return best;
}

3.7 Check yourself

1. In the unique paths problem, why can we fill the DP table row by row from top-left to bottom-right?
2. For minimum path sum, what changes in the recurrence compared to counting paths?
3. When solving the triangle minimum path bottom-up, why do we update the DP array from left to right?
4. In the maximal square problem, what does $dp[i][j]dp[i][j]$ represent, and why do we take the minimum of three neighbours?
5. For the dungeon game, why must we fill the DP table backwards from the destination?

Chapter 4. Sequences: longest increasing subsequence

4.1 Subsequences and the LIS problem

A subsequence keeps the order of elements but may skip some of them. From 2,4,1,3 the subsequence 2,1,3 is valid because the indices increase, while 3,1 is not because the order flips.

The longest increasing subsequence problem asks for the longest subsequence whose values also increase. Formally we want indices with and $kk$ as large as possible. This is exactly the problem Longest Increasing Subsequence from the sheet.

4.2 The quadratic DP

Dynamic programming builds a solution from smaller answers. Let $d[i]d[i]$ be the length of the longest increasing subsequence that ends exactly at position $ii$. Then $d[i]d[i]$ is 1 by itself, or it can be extended from an earlier with .

The answer is ${\max }_{i}d[i]\backslash max\_i\; d[i]$.

For $a=\{8,3,4,6,5,2,0,7,9,1\}a\; =\; \backslash \{8,3,4,6,5,2,0,7,9,1\backslash \}$ we get $d=\{1,1,2,3,3,1,1,4,5,2\}d\; =\; \backslash \{1,1,2,3,3,1,1,4,5,2\backslash \}$. The longest length is 5, e.g. 3,4,5,7,9. This method uses $O(n^2)O(n^2)$ time and $O(n)O(n)$ space.

def lis_length(a):
    n = len(a)
    d = [1]*n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                if d[j] + 1 > d[i]:
                    d[i] = d[j] + 1
    return max(d) if d else 0

assert lis_length([8,3,4,6,5,2,0,7,9,1]) == 5
assert lis_length([1,2,3,4]) == 4

int lis_length(vector<int> const& a){
    int n = (int)a.size();
    vector<int> d(n,1);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(a[j] < a[i]) d[i] = max(d[i], d[j]+1);
        }
    }
    int ans = 0;
    for(int v:d) ans = max(ans,v);
    return ans;
}

4.3 The faster tails idea

Binary search finds a position in a sorted list in logarithmic time.

Keep tails[l] as the smallest possible last value of an increasing subsequence of length $l+1l+1$ seen so far. The array stays sorted.

Processing 8,3,4,6,5,2,0,7,9,1:

step   tails
8      [8]
3      [3]
4      [3,4]
6      [3,4,6]
5      [3,4,5]
2      [2,4,5]
0      [0,4,5]
7      [0,4,5,7]
9      [0,4,5,7,9]
1      [0,1,5,7,9]

For each $xx$ we binary search the first $tailstails$ entry $\ge x\backslash ge\; x$ and replace it, or append if $xx$ is larger than all. The length of tails is the LIS length. This is $O(n\log n)O(n\backslash log\; n)$ time and $O(n)O(n)$ space.

import bisect
def lis_len_nlogn(a):
    d = []
    for x in a:
        i = bisect.bisect_left(d, x)
        if i == len(d):
            d.append(x)
        else:
            d[i] = x
    return len(d)

assert lis_len_nlogn([8,3,4,6,5,2,0,7,9,1]) == 5
assert lis_len_nlogn([3,4,2,5,1]) == 3