Dynamic Programming

House values are [2, 7, 9], and two adjacent houses can't both be robbed. Look at the last house (9); there are two choices. Skip it, and the answer is the best for the first two houses alone, 7. Rob it, and the second house is off limits, so add it to the best for the first house alone, 2: 2 + 9 = 11. The larger is 11. Spell out these two choices before writing the state and the transition.

Dynamic programming stores answers to repeated subproblems so later work can reuse them. Top-down memoization computes a state recursively and caches its result. Bottom-up tabulation computes dependencies before the states that need them. Both start with a precise state definition and recurrence.

Every solution has to respect three principles:

1. The definition of dp[i] decides everything. First write, in one sentence, what dp[i] means: ending at i, the prefix of length i, starting from i, or the range [i, j]. The base case, the induction rule, the fill order and where the answer lives all follow from that sentence. Change the definition and all four change with it.
2. Before you fill a cell, every cell it depends on must already be filled. If the induction rule looks left, fill left to right; if it looks right, fill right to left. When the order is hard to state, hand it to recursion + memo and let the call stack sort it out.
3. Every possible solution must land in some cell, and counting problems must not count anything twice. "Must end at i", "enumerate where the last cut goes" and "consider coins in a fixed order" all exist so that every case is covered exactly once.

The article goes in this order, and each step adds exactly one idea:

When to Use This Pattern

The brute force is usually a recursion tree that tries every choice at every step (rob or skip, where to jump, where the last cut goes). It is slow because the same argument gets computed many times. Take Fibonacci, f(5) = f(4) + f(3), and count how often each argument is called:

Without memo the number of calls is O(2^n); with memo each argument is computed once, O(n). A quick way to estimate any DP: number of states × cells each state looks back at × cost of looking at one cell.

Recognition Checklist

• The problem asks for an optimum, a count, or true/false, not a list of every solution
• The answer to the big problem can be assembled from answers to problems one size smaller
• When you draw the recursion tree, the same argument shows up more than once
• The state fits in one or two indices: a position, a length, two prefixes, a range, remaining capacity
• Each step has only a few choices: take or skip, where to cut, match or not
• Input size is around 10^3 to 10^4, so O(n²) or O(n·m) is fine

Before You Code

Before writing code, answer these four questions on paper. The first three are the DP definition, base case and induction rule; the fourth, "where is the answer", gets its own line because it is the easiest one to get wrong. Once the four answers are written down, the code is mostly transcription.

1. What does dp[i] mean? One plain sentence. The common shapes are: ending at i (must include i), the prefix of length i, and starting from i. If i is an index the array has n cells. If i is a length it has n + 1, because a length can be any of 0..n, which is n + 1 values; the extra dp[0] is the empty prefix, and the last element covered by dp[i] is s[i-1].
2. Which cells are the base case? The smallest ones, which you can write down without reading any other cell, such as dp[0], dp[0][j], dp[i][0].
3. Which cells does the induction rule look back at? Say it in words first, then as a formula. The direction you look back decides the fill order.
4. Which cell holds the answer? If the definition is a prefix, or the value only ever carries forward and never restarts, the answer is in the last cell. If the definition says "ending at i" and the value can restart, the answer is the maximum over the whole table.

The four answers form a chain: once the sentence in question 1 is clear, question 2 is that sentence at the smallest size, question 3 is that sentence going from one size smaller to the current size, and question 4 depends on whether the sentence says "must include i".

Try it on the longest ascending subarray: a = [7, 2, 3, 1, 5, 8, 9, 6]. The longest contiguous ascending run is [1, 5, 8, 9], so the answer is 4.

• Meaning: dp[i] = length of the longest ascending subarray that ends at a[i] and must include it. Why must it include a[i]? A subarray is contiguous, so a[i] can only extend the run that ends at a[i-1]. If dp[i-1] didn't promise to end at a[i-1], you couldn't tell whether a[i] connects to it.
• Base case: dp[0] = 1, a single number.
• Induction rule: if a[i] > a[i-1], extend the previous run, dp[i] = dp[i-1] + 1; otherwise start over at i, dp[i] = 1. It only looks one cell to the left, so fill left to right.
• Answer: the value can restart, so the longest run doesn't have to end at the last number (here dp[7] = 1). The answer is max(dp).

Step 2 turns this into code.

House Robber (LeetCode 198)

Given a line of nonnegative house amounts, return the maximum total from nonadjacent positions, allowing no selections; do not return indices. Adjacency follows the original order. The first and last houses are not neighbors in this linear version.

Input: nums = [2, 1, 4, 5]. Expected: 7 (houses 0 and 3).

dp[i] = the most money you can take from houses 0..i, with no two adjacent houses. For house i, either skip it (dp[i-1]) or take it (dp[i-2] + nums[i]).

1. Walk it by hand

2. Read the rule off the table

• The first two cells are filled directly: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
• From i = 2 on, every row compares two numbers, skip (dp[i-1]) and take (dp[i-2] + nums[i]), and keeps the larger one.
• Each row only reads cells to its left, so filling left to right always works. The answer is the last cell.

3. Turn each row into code

def rob(nums):
    if len(nums) == 1:
        return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[-1]

Core Templates

Every step uses the same approach: answer the four questions above, then check the three principles from the top. Can the definition be said in one sentence? Are the cells you depend on already filled? Did you miss any case?

Step 1: 1D linear, look back one or two cells

Problem: House Robber (LC 198). A row of houses; you can't rob two adjacent ones. What's the most you can take?

The input is an array nums of nonnegative integers, where nums[i] is the money in house i. Return the largest total you can take without robbing two adjacent houses. Return the amount, not house indices. Robbing nothing is allowed.

For example, [2, 7, 9, 3, 1] → 12: rob houses 0, 2 and 4, 2 + 9 + 1 = 12.

LeetCode guarantees a nonempty array. Below, rob_memo also returns 0 for an empty array, while rob requires a nonempty one.

The questions:

• Meaning: dp[i] = the most you can take from houses 0..i (house i included in the range) without robbing two adjacent ones. It does not require robbing house i. i is an index, so the array has n cells.
• Base case: dp[0] = nums[0], one house, rob it; dp[1] = max(nums[0], nums[1]), two houses, you can rob only one, so take the bigger.
• Induction rule: for house i, either skip it and inherit dp[i-1], or rob it, which rules out house i-1, giving dp[i-2] + nums[i]. Take the larger. It looks back two cells, so fill left to right.
• Answer: dp[n-1]. The definition is "only houses 0..i" and doesn't require robbing house i, so the value carries forward and never restarts.

Don't open a table yet. Recursion is the natural way to think from the top: f(i) trusts that f(i-1) and f(i-2) are already solved and only decides about the current house. Add a memo so each i is computed once:

from functools import lru_cache


def rob_memo(nums):
    @lru_cache(maxsize=None)        # remember the result for each i; never recompute the same i
    def f(i):                       # f(i) = most money from houses 0..i
        if i < 0:                   # no houses left
            return 0
        return max(f(i - 1), f(i - 2) + nums[i])   # skip i / rob i
    return f(len(nums) - 1)


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

@lru_cache(maxsize=None) is a decorator, written on the line above the function. The second time f gets the same argument, it returns the stored result without running the body again; maxsize=None means the cache has no size limit. It is the memo table.

Translating the recursion into a table is a one-to-one mapping:

In the recursion a single i < 0 covers both edges: f(0) reads f(-2) and f(1) reads f(-1), and both return 0. The table has no cells -1 and -2, and dp[i] reads two cells back, so the base case has to give two cells directly, dp[0] and dp[1], and the loop starts at i = 2:

def rob(nums):
    if len(nums) == 1:              # with one house there is no dp[1], return directly
        return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])   # we read two cells back, so seed two cells
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])   # skip i / rob i
    return dp[-1]                   # never restarts, answer is the last cell


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

dp[-1] is a Python negative index: it counts from the end, so it is dp[n-1].

Filling the table for nums = [2, 7, 9, 3, 1]:

Principle 2: dp[i] only reads the two cells to its left, which are always filled when you go left to right. Principle 3: every valid plan either robs the last house or doesn't, so it lands in "rob" or "skip".

O(n) time, O(n) space.

One more like it: Climbing Stairs (LC 70)

The input is a positive integer n. Each move climbs 1 or 2 steps. Return the number of ways to reach exactly step n. The same steps in a different order count as different ways.

For example, n = 3 → 3: 1+1+1, 1+2, 2+1.

Think first: What does dp[i] mean? The last move onto step i could come from which steps? Do those groups overlap, so do you add them or take the max? Should dp[0] be 0 or 1?

def climb_stairs(n):
    prev2, prev1 = 1, 1             # dp[0], dp[1]
    for _ in range(2, n + 1):       # _: the loop variable is unused
        prev2, prev1 = prev1, prev1 + prev2   # one step from i-1 + two steps from i-2
    return prev1


assert climb_stairs(1) == 1
assert climb_stairs(2) == 2
assert climb_stairs(3) == 3         # the example from the statement
assert climb_stairs(5) == 8

Variant: houses in a circle (LC 213)

The input is an array of nonnegative integers, but the houses form a circle, so the first and last houses are neighbors too. Everything else is the same as LC 198: return the largest total.

For example, [2, 3, 2] → 3: houses 0 and 2 are neighbors around the circle and can't both be robbed, so the best is the 3 in the middle. A single house [5] → 5: a house is not its own neighbor.

Think first: Compared with LC 198 there is one extra rule: the two ends can't both be robbed. Can you split this into a few cases where each one is LC 198 on a straight row? Do those cases together miss any plan?

def rob_circle(nums):
    if len(nums) == 1:              # [5][:-1] is empty, and rob doesn't accept an empty array
        return nums[0]
    return max(rob(nums[:-1]), rob(nums[1:]))   # skip the last / skip the first


assert rob_circle([2, 3, 2]) == 3
assert rob_circle([1, 2, 3, 1]) == 4
assert rob_circle([10, 1, 1, 30]) == 31
assert rob_circle([5]) == 5         # the example from the statement
assert rob_circle([7]) == 7

Step 1 recap

• What it solves: optimum or count problems where each step has a few choices and depends only on the previous one or two cells.
• The key line: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); if you look back two cells, seed two base cells.
• What the variants change: Climbing Stairs replaces max with addition and sets dp[0] = 1; the circle splits into "skip the last house" and "skip the first house", two straight rows, each solved by 198.
• Easiest mistake: writing dp[1] = nums[1]. dp[1] means "only houses 0..1" and doesn't require robbing house 1, so it must be max(nums[0], nums[1]); otherwise [5, 1] returns 1 instead of 5.

Step 1 defines dp[i] over "houses 0..i", so the answer is naturally the last cell. When the problem wants a contiguous run, the definition must become "must end at i", and the answer moves too. That's Step 2.

Step 2: Ending at i, the answer is the max over the table

Problem: Longest ascending subarray (the one from the questions above). a = [7, 2, 3, 1, 5, 8, 9, 6], return 4.

The questions are already answered: dp[i] = length of the longest ascending subarray that ends at and includes a[i]; dp[0] = 1; extend with dp[i-1] + 1 if you can, otherwise restart at 1; the answer is max(dp).

The only new thing in this step: when the definition says "must include i", the answer has to be found across the whole table. The code tracks it in best as it fills:

def longest_ascending_subarray(a):
    if not a:
        return 0
    dp = [1] * len(a)               # dp[i] = longest ascending run ending at a[i]; each number alone has length 1
    best = 1
    for i in range(1, len(a)):
        if a[i] > a[i - 1]:
            dp[i] = dp[i - 1] + 1   # extend the run that ends at a[i-1]
        else:
            dp[i] = 1               # can't extend, restart at i
        best = max(best, dp[i])
    return best                     # restarts happen, so take the max over the table


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

The whole dp starts at 1: every number on its own is an ascending subarray of length 1. That also fills the base case dp[0] = 1, so the loop starts at i = 1.

If the last line were return dp[-1], this example would return 1.

Why the definition must say "must include i". Switch to dp[i] = "length of the longest ascending subarray within a[0..i]" (not required to include i), keep the same rule, and try [1, 2, 0, 3]:

dp[2] = 2 describes [1, 2], which doesn't end at 0, so 3 can't be appended to it. The definition didn't say what the run ends with, and the rule glued the wrong pieces together.

One more like it: Maximum Subarray (LC 53, Kadane)

The input is a nonempty integer array a. Return the largest sum of a nonempty contiguous subarray. Return the sum, not the subarray.

For example, [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6, from [4, -1, 2, 1]. Even when everything is negative you must pick at least one number: [-3, -1] → -1, not the 0 of an empty subarray.

Think first: It's contiguous, so define it as "ending at a[i]", as above. A subarray ending at a[i] can come from which two places? When should you drop the run before it and restart at a[i]? Can best start at 0?

def max_subarray(a):
    cur = best = a[0]               # cur is dp[i-1]; best must not start at 0
    for x in a[1:]:                 # a[1:] is the slice without element 0
        cur = max(cur + x, x)       # extend the previous run / restart at x
        best = max(best, cur)
    return best


assert max_subarray([2, -1, 4, -2, 1]) == 5
assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray([-3, -1]) == -1     # the example from the statement
assert max_subarray([-2, -1, -3]) == -1
assert max_subarray([3]) == 3

Variant: Maximum Product Subarray (LC 152)

The input is a nonempty integer array, which may contain 0 and negative numbers. Return the largest product of a nonempty contiguous subarray.

For example, [2, 3, -2, 4] → 6, from [2, 3]. [-2, 0, -1] → 0: the two negatives are separated by a 0, and you can't skip the 0 to multiply them, so the best is the 0 by itself.

Think first: Still "ending at a[i]". Is it enough to track only "the largest product ending at i", as in LC 53? When you multiply by a negative number, which value from the previous cell can become the new largest product?

def max_product(a):
    hi = lo = best = a[0]           # largest and smallest product ending at i
    for x in a[1:]:
        cands = (x, hi * x, lo * x)  # restart / extend the max / extend the min
        hi, lo = max(cands), min(cands)   # update together, both use last round's values
        best = max(best, hi)
    return best


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

Step 2 recap

• What it solves: longest or largest contiguous subarray or substring.
• The key line: best = max(best, dp[i]). The definition is "ends at and includes a[i]", so the answer is the table maximum, not dp[-1].
• What the variants change: LC 53 replaces "extend means +1" with "extend or restart, take the larger"; LC 152 also tracks the smallest product, because a negative number flips large and small.
• Easiest mistake: starting best at 0. An all-negative array then returns 0; start from a[0].

So far every dp[i] looks left and the table is always filled left to right. That direction isn't fixed; it follows the definition. That's Step 3.

Step 3: Same problem, different definition, and the fill direction flips

Problem : Jump Game ( LC 55 ). nums[i] is the farthest you can jump to the right from i. (Pro lesson)

One more like it: fewest jumps (LC 45)

The input is an array nums of nonnegative integers, where nums[i] is the farthest you can jump right from i. (Pro lesson)

Variant: when the dependency order is hard to state, use recursion + memo (LC 329)

The input is a nonempty integer matrix matrix . Each move goes one cell up, down, left or right, and the next cell's value must be strictly… (Pro lesson)

Step 3 recap

What it solves : the same problem can have different dp definitions, and the fill direction follows the definition instead of always running… (Pro lesson)

Step 4: Look back at every j < i: left big part from the table, right small part computed directly

Problem : Integer Break ( LC 343 ). Cut a rope of length n at least once into integer-length pieces; maximize the product of the lengths. (Pro lesson)

One more like it: Word Break (LC 139)

The input is a nonempty string s and a list of words word_dict (called wordDict on LeetCode). (Pro lesson)

One more like it: Decode Ways (LC 91)

Digits map to letters as '1' → A, '2' → B, …, '26' → Z. The input is a nonempty digit string s . (Pro lesson)

Variant: j is "the previous element", not a cut (LC 300)

The input is an integer array nums . Return the length of the longest strictly increasing subsequence. (Pro lesson)

Variant: counting problems must not double count (LC 940)

The input is a string s of lowercase letters. Return how many distinct nonempty subsequences it has. (Pro lesson)

Step 4 recap

What it solves : problems that look back at every shorter prefix: cutting, splitting into dictionary words, subsequences. (Pro lesson)

Step 5: Two indices dp[i][j], look back left, up, and up-left

Problem : Longest Common Subsequence ( LC 1143 ). a = "abcde" , b = "ace" , return 3. The input is two strings. (Pro lesson)

Contrast: Longest Common Substring (must be contiguous)

The input is two strings a and b . Return the length of their longest common substring . A substring must be contiguous; (Pro lesson)

One more like it: Edit Distance (LC 72)

The input is two strings a and b , either of which may be empty. (Pro lesson)

One more like it: grid paths (LC 62)

The input is positive integers m and n, a grid with m rows and n columns. (Pro lesson)

Variant: with (i, j) as the bottom-right corner (LC 221)

The input is a matrix of "0" and "1" (each element is a string, not an integer). (Pro lesson)

Step 5 recap

What it solves : comparing, matching or editing two strings, or walking a grid and finding squares. (Pro lesson)

Step 6: Knapsack, where loop order is the meaning

Problem : Partition Equal Subset Sum ( LC 416 ). (Pro lesson)

Turn it around: unbounded knapsack (LC 322)

The input is an array coins of distinct positive denominations and a nonnegative integer amount . (Pro lesson)

One step further: which loop is outside (LC 518 vs LC 377)

Both problems give a set of distinct positive integers, each usable any number of times, and ask how many ways there are to reach a target s… (Pro lesson)

Step 6 recap

What it solves : a capacity or amount limit and items to choose from; can you make it, how few, how many ways. (Pro lesson)

Advanced: when one cell can't hold enough, add a dimension

So far the state has been a position (plus a capacity, at most). (Pro lesson)

State machine: stock with cooldown (LC 309)

The input is the daily stock prices prices . You may buy and sell many times, but you hold at most one share, so you must sell before buying… (Pro lesson)

Interval DP: counting palindromic substrings (LC 647)

The input is a string s . Return the number of palindromic substrings. A substring must be contiguous; (Pro lesson)

Games: Stone Game (LC 877)

The input is an even number of piles piles , each a positive integer, with an odd total, so there are no ties. (Pro lesson)

Interval DP: enumerate the last move (LC 312)

The input is an array nums of nonnegative integers, each the value of a balloon, and you must burst every balloon. (Pro lesson)

Advanced recap

What it solves : information that doesn't fit in one cell (holding a stock or not, which range, whose turn) goes into the state. (Pro lesson)

The six steps together

Step dp definition Looks back at Fill order Answer Step 1 only 0..i i-1, i-2 left to right last cell Step 2 ending at i, must include i i-1… (Pro lesson)

One Problem, Many Disguises

Disguise (how the problem says it) Translate to the core problem Step Climb 1 or 2 steps at a time, how many ways (70) dp[i] = dp[i-1] + dp[… (Pro lesson)

Common Pitfalls

i is a length but you allocate only n cells. dp = [False] * len(s) with dp[i] meaning the prefix of length i leaves no cell for length n, or… (Pro lesson)

Say It in the Interview

State what dp[i] means first, then the base case, the transition and where the answer is, and finish with the complexity: I'll use dynamic p… (Pro lesson)