1D DP Problems

Ask what the last decision needs to know

A street has 100 houses in a row, each with some cash inside. Neighbouring houses share an alarm, so you can never rob two houses that stand next to each other. How much can you take?

The obvious plans fail quickly. Richest house first fails on [2, 3, 2]: you grab the 3, both 2s become off-limits, and you miss 2 + 2 = 4. Every other house fails on [2, 1, 1, 2]: the even positions give 3, the odd positions give 3, and houses 0 and 3 together give 4. Try every legal plan is correct, but a street of 100 houses has 927,372,692,193,078,999,176 legal plans, about 9.3 × 10²⁰.

Now stand at the last house and ask what the decision there actually needs to know. Skip it, and your total is the best you can do with the first 99 houses. Rob it, and house 98 is off-limits, so your total is its cash plus the best you can do with the first 98 houses. Two numbers about shorter streets settle the whole street. So compute the best for 1 house, then 2, then 3, each from the two before it. A hundred houses take a hundred small steps.

That is 1D dynamic programming: give every index one number, say in a sentence exactly what that number means, and compute it from a few earlier numbers. The skill is choosing the sentence. This lesson teaches five sentences that cover most one-dimensional DP problems on LeetCode:

Before you start. Dynamic Programming Mastery covers the general machinery: overlapping subproblems, memoization versus tabulation, and why a table beats plain recursion. This lesson applies it to one-dimensional problems and recaps it only where a problem needs it. Two habits from Foundation: Arrays & Strings come back here. Its running summary was already a DP whose whole state fit in two variables (the cheapest price so far and the best profit), and its prefix convention (prefix[k] covers the first k elements, prefix[0] is the empty prefix) returns as dp[0]. If the call stack is hazy, Advanced Recursion & Backtracking explains it.

The recipe: five answers before any code

Every solution in this lesson answers the same five questions. Answer them in words first, and the code becomes a translation.

1. State. Finish the sentence "dp[i] is the ___ of ___." Three main shapes of index cover this lesson:

   • Prefix length: dp[i] describes the first i items (nums[:i], s[:i]). The table has n + 1 cells, dp[0] is the empty prefix, and the answer is dp[n]. Its mirror image, the suffix (dp[i] describes items i to the end, filled from the right), appears in Move 2.
   • Ending exactly at i: dp[i] describes solutions whose last chosen item is nums[i]. The table has n cells, and the answer is usually max(dp), because the best solution can end anywhere.
   • Value: dp[a] describes a target total a. The table has target + 1 cells, and the input's length doesn't size it at all.

2. Transition. Look at the last decision of any solution for state i: the last hop, the last house, the last coin, the last word. Each option for that decision leaves a smaller state that is already solved.

3. Combine. The question decides the operator you apply across the options:

   The question asks	Combine the options with	A cell updated in place starts at
   How many ways?	sum	0
   Cheapest? Fewest?	min	+∞ ("unreachable")
   Most? Longest?	max	the value of an option that is always available (choosing nothing, or LIS's one-element subsequence); −∞ only if there is none
   Is it possible?	any (logical or)	False

   A + can still appear inside an option: dp[a - c] + 1 adds a coin, best[k - 2] + nums[k - 1] adds a house. Counting and optimizing differ in the operator between options. The last column matters only for cells you update in place (dp[a] = min(dp[a], …)); a cell assigned in one go from finished values needs no special start.

4. Base cells. Some cells have no smaller state to come from. Usually that is the empty state, and the sentence from step 1 tells you its value: one way to climb zero stairs (do nothing), zero coins to make zero, True for splitting the empty string into zero words.

5. Order and answer. Fill cells so each one is written before anything reads it (increasing index for the worked problems here; Move 2 shows when to fill from the right), and know where the answer sits: dp[n], dp[target] or max(dp).

Cost is (number of states) × (work per state) for time, and the table for space. When every transition looks back a fixed distance, the table shrinks to a few variables.

🧠 The notebook again. The stock trader in the Foundation lesson kept a notebook of two numbers: the cheapest price so far and the best profit. A DP table is the same notebook with one line per index. Before you write code, write the sentence for a single line.

Move 1: Count or price the last step

Smell: the last move into position i came from one of a few fixed earlier positions.

The staircase

You climb a staircase of n steps, one or two steps per hop. How many different hop sequences reach the top? This is LeetCode 70: Climbing Stairs.

Predict first: how many ways are there for n = 4? And why does ways(4) = ways(3) + ways(2) never count a climb twice?

That argument is the whole method for counting problems: split by the last decision, check that the groups don't overlap and miss nothing, then add.

The slow version writes the argument as recursion:

def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

It is correct and hopeless. ways(45) makes 3,672,623,805 calls, which took about a minute and a half of CPython on a fast laptop. The calls repeat: inside ways(10), ways(5) is computed 8 times and ways(2) 34 times. In total the recursion makes 2·ways(n) − 1 calls, so the work grows exactly as fast as the answer, about 1.6× per extra step.

The fast version computes each step once, from the bottom up:

def climb_stairs(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)          # dp[i] = number of ways to stand on step i
    dp[0], dp[1] = 1, 1         # the empty climb; a single 1-hop
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # last hop was 1, or last hop was 2
    return dp[n]

Why is dp[0] = 1? There is exactly one way to be standing on the ground: do nothing. dp[0] is not padding. It is the empty climb, and it is what makes dp[2] = dp[1] + dp[0] = 2 come out right. For n = 7 the table is 1, 1, 2, 3, 5, 8, 13, 21.

Each cell reads only the two before it, so two variables are enough:

def climb_stairs(n):
    two_back, one_back = 1, 1               # ways(0), ways(1)
    for _ in range(2, n + 1):
        two_back, one_back = one_back, one_back + two_back
    return one_back

That is O(n) time and O(1) extra space. ⚠️ The tuple assignment does real work: Python evaluates both right-hand values before it changes either name. Split it into one_back = one_back + two_back followed by two_back = one_back, and two_back receives the new value. The sequence then doubles every step, and n = 5 returns 16 instead of 8.

Integer size. Python integers never overflow. In Java or C++ they do: ways(45) = 1,836,311,903 fits in a signed 32-bit int, but ways(46) = 2,971,215,073 does not. LeetCode caps n at 45, the last value whose answer fits.

Memoizing, and Python's call stack

Adding a cache to the slow version also makes it O(n), because each n is now computed once:

from functools import cache

@cache
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

The catch is depth. The first call waits on ways(n - 1), which waits on ways(n - 2), and so on: a chain of about n unfinished calls. Python's default recursion limit is 1000 (sys.getrecursionlimit()), so in a fresh CPython 3.12+ interpreter this raises RecursionError from about ways(1000) on. On 3.11 and earlier, the cache wrapper's own calls counted against the limit too, and the failure came at about ways(500). The cache costs O(n) space, and the pending calls cost another O(n) of stack.

sys.setrecursionlimit(...) is the usual workaround, and it helps only up to a point. How far depends on the Python version, the operating system's stack size and what each call costs. On our test machine (CPython 3.14 on macOS), with the limit raised to a million, this @cache version still failed with a stack-overflow RecursionError near depth 8,000, while a hand-written dictionary memo reached 200,000. A loop has no depth at all. When n can be large, fill the table bottom-up.

Same staircase, now with prices

In LeetCode 746: Min Cost Climbing Stairs, cost[i] is the fee for stair i. You may start on stair 0 or stair 1 for free, hop one or two stairs at a time, and must reach the top: position n, just past the last stair. What is the cheapest total?

The question changed from "how many" to "cheapest", so the operator changes from sum to min. The other change is easy to miss: the sentence must say exactly when a fee is paid. Here is one sentence, where you pay a stair's fee when you leave it:

dp[i] = the cheapest total to be standing on position i, having paid for every stair you left.

def min_cost_climbing_stairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)      # dp[i] = cheapest way to stand on position i; n is the top
    # dp[0] = dp[1] = 0: starting on stair 0 or 1 is free
    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + cost[i - 1],   # hop 1 from stair i-1, paying its fee
                    dp[i - 2] + cost[i - 2])   # hop 2 from stair i-2, paying its fee
    return dp[n]

For cost = [10, 15, 20]:

The answer is 15: start on stair 1, pay 15, and hop two stairs to the top. On LeetCode's longer example, [1, 100, 1, 1, 1, 100, 1, 1, 100, 1], it returns 6.

A second sentence works too: pay a stair's fee when you land on it. Then paid[i] = the cheapest total to stand on stair i with its own fee included, so paid[0] = cost[0], paid[1] = cost[1] and paid[i] = cost[i] + min(paid[i - 1], paid[i - 2]). The top has no fee and can be reached from either of the last two stairs, so the answer is min(paid[n - 1], paid[n - 2]). The answers are the same; the table is different.

⚠️ Mixing the two sentences is the classic bug. Run the pay-on-landing formula min(dp[i - 1], dp[i - 2]) + cost[i] all the way to the top at i = n, and it reads cost[n], which does not exist: IndexError. Patch the top with cost[i] if i < n else 0 but borrow the free-start base cases dp[0] = dp[1] = 0 from the other sentence, and stairs 0 and 1 are never paid for: [10, 15, 20] returns 0. Base cases are not a separate decision. They follow from the sentence.

Your turn: hops may now be 1, 3 or 5 steps long. How many ways are there to climb 6 steps? Write the loop. Which cells are base cells, and what guard does the transition need?

def climb_135(n):
    dp = [0] * (n + 1)
    dp[0] = 1                       # the empty climb is the only base cell
    for i in range(1, n + 1):
        for hop in (1, 3, 5):
            if hop <= i:            # a hop can't start below the ground
                dp[i] += dp[i - hop]
    return dp[n]

Move 2: Take it or skip it

Smell: each item is either chosen or not, and choosing one rules out its neighbours.

The robber's street, solved

Back to the opening problem: LeetCode 198: House Robber.

Predict first: for nums = [2, 7, 9, 3, 1], what is the best total, and which houses make it?

Use the prefix-length shape: best[k] = the most money you can take from the first k houses (houses 0 to k − 1). The last decision is about house k - 1:

• skip it: the plan is a plan for the first k - 1 houses, worth best[k - 1];
• take it: house k - 2 is off-limits, so the rest is a plan for the first k - 2 houses, worth best[k - 2] + nums[k - 1].

def rob(nums):
    n = len(nums)
    best = [0] * (n + 1)        # best[k] = most money from the first k houses
    if n >= 1:
        best[1] = nums[0]       # one house: take it
    for k in range(2, n + 1):
        best[k] = max(best[k - 1],                 # skip house k-1
                      best[k - 2] + nums[k - 1])   # take house k-1
    return best[n]

For [2, 7, 9, 3, 1] the table is [0, 2, 7, 11, 11, 12]. Each cell reads two earlier ones, so two variables are enough again:

def rob(nums):
    two_back, one_back = 0, 0           # best[k-2], best[k-1]
    for x in nums:
        two_back, one_back = one_back, max(one_back, two_back + x)
    return one_back

An empty street returns 0 with no special case. That is O(n) time and O(1) extra space.

Why two numbers are enough

Take any best plan for the first k houses. If it skips house k - 1, it is a legal plan for the first k - 1 houses, so it is worth at most best[k - 1]. If it takes house k - 1, it cannot take house k - 2, so the rest of it is a legal plan for the first k - 2 houses, worth at most best[k - 2]. Both totals can actually be reached, so the larger one is exactly best[k]. That is optimal substructure in two sentences: the rest of a best plan must itself be a best plan for its shorter street, or you could swap in a better one.

⚠️ The off-by-one base case. Many solutions index by house instead: dp[i] = the best using houses 0 to i. Then dp[1] is the best from the first two houses, which is max(nums[0], nums[1]), not nums[1]. With dp[1] = nums[1], [2, 1, 1, 2] returns 3 instead of 4, because the table never learns that house 0 alone beats house 1. The prefix-length version needs no such special case: best[0] = 0 does the work.

Which houses? Keep the full table and walk backwards. If best[k] == best[k - 1], some best plan skips house k - 1; otherwise house k - 1 must be taken, and you jump to k - 2:

def rob_plan(nums):
    n = len(nums)
    best = [0] * (n + 1)
    if n >= 1:
        best[1] = nums[0]
    for k in range(2, n + 1):
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    plan, k = [], n
    while k > 0:
        if best[k] == best[k - 1]:
            k -= 1                  # a best plan skips house k-1
        else:
            plan.append(k - 1)      # house k-1 must be taken
            k -= 2
    return plan[::-1]

For [2, 7, 9, 3, 1] it returns [0, 2, 4]. The rolling version can't do this, because it has thrown the table away.

The jump is the only thing that changes

"Take" jumps back past everything the chosen item conflicts with. For houses, the jump lands on k - 2. Change the conflict rule and only the jump moves:

• If robbing a house also alarms the houses two doors away, "take" jumps to best[k - 3].
• If the items are sorted values or time intervals and "conflict" means "too close", "take" jumps to the last compatible item. A pointer that only moves forward, or a binary search (bisect, see Move 5), finds it.
• If the rule points forwards ("choosing item i blocks the next p items"), fill from the right. Let dp[i] be the best from item i to the end; then "take" reads dp[i + p + 1], clamped at n.

⚠️ A memo that remembers the wrong street. A top-down version is tempting to write with a default-argument dictionary:

def rob_from(nums, i, memo={}):         # BUG: one dict shared by every call
    if i >= len(nums):
        return 0
    if i in memo:
        return memo[i]
    memo[i] = max(rob_from(nums, i + 1), nums[i] + rob_from(nums, i + 2))
    return memo[i]

print(rob_from([2, 7, 9, 3, 1], 0))   # 12
print(rob_from([1, 1, 1], 0))         # 12 again: the first street's answer

Python creates a default value once, when def runs, so every call shares the same dictionary. The key i doesn't mention nums, so the second street reads the first street's answers (the right answer is 2). LeetCode runs many test cases in one process, so this fails there too. Create the cache inside the function (for example @cache on a nested helper), or key it on everything the answer depends on.

Test it like a professional

When inputs are small, a brute-force reference takes a few lines. Represent a plan as a bitmask; mask & (mask >> 1) is non-zero exactly when two neighbouring bits are both set:

import random

def rob_reference(nums):
    n, best = len(nums), 0
    for mask in range(1 << n):              # every subset of houses
        if mask & (mask >> 1):              # two neighbours chosen: illegal
            continue
        best = max(best, sum(nums[i] for i in range(n) if mask >> i & 1))
    return best

for _ in range(500):
    nums = [random.randint(0, 20) for _ in range(random.randint(0, 10))]
    assert rob(nums) == rob_reference(nums), nums
print("all matched")

Plot twist: the street is a circle

In LeetCode 213: House Robber II the houses stand in a circle, so the first and last houses are neighbours too.

You don't need a new recurrence. You need a case split. No legal plan takes both house 0 and house n - 1, so every plan leaves out at least one of them. Solve the street without house 0, solve it without house n - 1, and keep the larger answer:

def rob_circle(nums):
    if len(nums) == 1:
        return nums[0]                  # both slices would be empty
    return max(rob(nums[1:]),           # house 0 left out
               rob(nums[:-1]))          # house n-1 left out

Why two cases are enough: every legal circle plan is a legal line plan in at least one of the two ranges, and every line plan in either range is legal on the circle, because it cannot contain both ends. Two linear passes give O(n) time. The slices copy the list, which is O(n) extra space; pass start and end indices instead if you need O(1).

Your turn: predict rob_circle for [2, 3, 2], [1, 2, 3, 1] and [5]. What would [5] return without the first if?

Move 3: Index by the amount

Smell: the problem names a target total, pieces can be reused, and the order of the pieces doesn't matter.

Greedy's blind spot

LeetCode 322: Coin Change: given coin values and an amount, return the fewest coins that sum to exactly the amount, or −1 if no handful works. You have unlimited coins of each value.

Predict first: coins [1, 3, 4], amount 6. What does "largest coin first" give, and what is the best?

The index is now a value: dp[a] = the fewest coins that sum to exactly a. The last coin is some c ≤ a, and what remains is the amount a - c:

dp[a] = 1 + min(dp[a - c] for every coin c ≤ a), with dp[0] = 0.

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

For coins = [1, 2, 5] and amount = 11:

At a = 11 the three last-coin options give dp[10] + 1 = 3, dp[9] + 1 = 4 and dp[6] + 1 = 3. The answer is 3, for example 5 + 5 + 1.

Why it works. A best handful for a has some last coin c. The other coins make a - c, and they must be a best handful for it, or you could swap in a smaller one. Trying every c covers every possible last coin.

Cost. O(amount × k) time, where k is the number of coin values, and O(amount) space. The look-back distance is a coin value, which can be anything up to amount, so rolling variables don't apply. Notice what sizes the table: the value of amount, not the length of any input. LeetCode keeps amount ≤ 10⁴, so the table has at most 10,001 cells. An amount of 10¹² would need 10¹² cells, and this method would be out.

Sentinels: where "unreachable" goes

dp[a] is updated in place by min, so it must start "worse than any real answer".

• float('inf') is fine in Python: inf + 1 is still inf, and it compares correctly with integers.
• amount + 1 works just as well and keeps the list all integers. No real answer uses more than amount coins, because every coin is worth at least 1.
• Start the table at 0 instead and min(0, anything) stays 0, so the function returns 0 for every amount.
• In Java or C++, don't use INT_MAX as the sentinel: INT_MAX + 1 overflows (in Java it wraps to the most negative int), and that value then wins every min.

House Robber's table starts at 0 harmlessly because each of its cells is assigned from two finished values, never updated in place.

⚠️ The negative-index trap, live. Remove the if c <= a guard and Python raises nothing: dp[a - c] with a negative index reads from the end of the list. With coins = [1, 2, 5] the wrapped cells still hold ∞, and amount 11 still gives 3, by luck. With coins = [5] and amount = 3, dp[1 - 5] is dp[-4], which is dp[0] = 0, so the function returns 3: three "coins" worth 5 that somehow make 3. With coins = [10] and amount = 3 it raises IndexError. One bug, three symptoms.

Counting instead: Coin Change II

LeetCode 518: Coin Change II asks for the number of combinations that make the amount. For amount 5 and coins [1, 2, 5] there are 4: 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.

The operator becomes a sum, and the base becomes ways[0] = 1, the empty handful. Now the loop order matters:

def change(amount, coins):
    ways = [0] * (amount + 1)   # ways[a] = combinations of the coins so far that sum to a
    ways[0] = 1                 # the empty handful
    for c in coins:                        # coins outside
        for a in range(c, amount + 1):     # amounts inside, going up
            ways[a] += ways[a - c]
    return ways[amount]

The table after each coin:

Why coins outside counts each combination once. While the outer loop is on coin c, the table counts only handfuls built from the coins processed so far. So every handful is assembled in one fixed order (all its 1s, then its 2s, then its 5s) and counted exactly once.

Swap the loops (amounts outside, coins inside) and every amount lets every coin be the last one, so 1 + 2 and 2 + 1 are both counted. That counts ordered sequences: 9 for amount 5, not 4. Ordered sequences are a real problem too, LeetCode 377: Combination Sum IV, and you will meet it in the final round.

The direction of the inner loop decides reuse. Going up, ways[a - c] has already been updated for coin c, so coin c can appear again: unlimited copies. Going down, ways[a - c] still holds its value from before coin c, so each coin is used at most once. With [1, 2, 5] and amount 5, the downward loop finds only {5}: 1 way. That downward loop is the classic "each item at most once" (0/1) subset-sum loop, and a boolean table with or in place of + answers "can some subset reach this total?".

For Coin Change's fewest coins, loop order doesn't matter: a handful has the same number of coins in any order, so the minimum over sequences equals the minimum over combinations.

Your turn: coins [2, 3], amount 8. Predict the fewest coins, the number of combinations and the number of ordered sequences. Then predict coin_change([2], 3).

Move 4: Cut a string into pieces

Smell: the string must be split into consecutive pieces, each piece can be checked on its own, and the question asks how many splits exist or whether one does.

Use the prefix-length shape: dp[i] = the answer for the first i characters, s[:i]. The last decision is the last piece, s[j:i], and dp[0] is the empty prefix. It is the Foundation lesson's prefix[0] again: a reading taken before any character.

Decode Ways

LeetCode 91: Decode Ways: the letters A to Z are encoded as "1" to "26". Given a string of digits, count the ways to decode it.

Predict first: how many decodings do "226", "2101" and "06" have?

The last piece is either one digit, s[i - 1], which is valid when it isn't '0', or two digits, s[i - 2:i], which are valid when they form a number from 10 to 26:

def num_decodings(s):
    n = len(s)
    dp = [0] * (n + 1)      # dp[i] = ways to decode the first i digits, s[:i]
    dp[0] = 1               # the empty prefix decodes one way: to nothing
    for i in range(1, n + 1):
        if s[i - 1] != '0':                          # last piece: one digit, 1-9
            dp[i] += dp[i - 1]
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:   # last piece: two digits, 10-26
            dp[i] += dp[i - 2]
    return dp[n]

Trace "11106":

The two decodings are 1 1 10 6 (AAJF) and 11 10 6 (KJF).

Zeros are the whole difficulty. A '0' can only be the second digit of 10 or 20. A leading '0' makes dp[1] = 0, and every count built on it collapses: "06" returns 0. "100" returns 0 as well, because the second zero has no partner. The range test on the integer handles pairs that start with zero: int("06") is 6, which fails 10 <= … <= 26.

Why it works. Every decoding has a last piece of one or two digits. The two groups can't overlap, and each group is (the decodings of the shorter prefix) followed by that one piece. It is the staircase argument again; only the rule for a legal hop changed.

Each cell reads the two before it, so the rolling version runs in O(n) time with O(1) extra space:

def num_decodings(s):
    two_back, one_back = 0, 1       # dp[i-2], dp[i-1]; one_back starts as dp[0]
    for i in range(1, len(s) + 1):
        cur = one_back if s[i - 1] != '0' else 0
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
            cur += two_back
        two_back, one_back = one_back, cur
    return one_back

Both versions return 1 for "", the empty decoding. LeetCode never passes an empty string.

Word Break

LeetCode 139: Word Break: can s be split into words from a dictionary, reusing words as often as you like?

Predict first: s = "abcd" with words = ["a", "abc", "b", "cd"]. Does "take the longest dictionary word that fits, then continue" find a split?

The question is now "is it possible?", so the operator is any, and the empty prefix is True:

def word_break(s, word_dict):
    words = set(word_dict)
    longest = max(map(len, words), default=0)
    n = len(s)
    ok = [False] * (n + 1)      # ok[i]: the first i characters split into words
    ok[0] = True                # the empty prefix needs zero words
    for i in range(1, n + 1):
        for j in range(max(0, i - longest), i):     # s[j:i] is the last word
            if ok[j] and s[j:i] in words:
                ok[i] = True
                break
    return ok[n]

For s = "catsanddog" with ["cat", "cats", "and", "sand", "dog"], the reachable cut points are 0, 3, 4, 7 and 10. Position 7 is reachable two ways (cat|sand and cats|and), and the table stores it once; that is the saving. For "catsandog" with the same words, the cut points are 0, 3, 4 and 7, and position 9 is never reached, so the answer is False.

Cost, honestly. A set lookup is expected O(1) per hash, but hashing a string of length m costs O(m), and each slice s[j:i] is a brand-new string that must be built and hashed. With the longest limit, each of the n end positions (n = len(s)) tries at most L start points (L = the longest word's length), and each slice costs O(L): O(n · L²) time, plus building the set, and O(n) for the table. Without the limit, j runs over every earlier position and slices can be n long: O(n³) in the worst case.

Where DP stops helping. LeetCode 140: Word Break II asks for every sentence, not a yes or no. The output itself can be exponential: "a" * 30 with words ["a", "aa"] has 1,346,269 splits, and no algorithm lists them faster than it can write them. The table still helps, by telling you which cut points can lead to a finish.

Your turn: fill dp[0..4] of num_decodings for "1212". Then do the same for "1202".

Move 5: The longest increasing subsequence

Smell: you pick a subsequence (skips allowed), and each chosen element must relate to the one chosen just before it.

LeetCode 300: Longest Increasing Subsequence asks for the length of the longest strictly increasing subsequence.

Predict first: what is the answer for [10, 9, 2, 5, 3, 7, 101, 18]? And why can't the state be "the LIS length of the first k elements"?

"Ends exactly here"

So put the last element into the state: end[i] = the length of the longest strictly increasing subsequence whose last element is nums[i]. The element before it is some nums[j] with j < i and nums[j] < nums[i]:

def length_of_lis(nums):
    if not nums:
        return 0
    end = [1] * len(nums)   # end[i] = longest increasing subsequence ending at index i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                end[i] = max(end[i], end[j] + 1)
    return max(end)

⚠️ Return max(end), not end[-1]. The best subsequence can end anywhere. On [1, 2, 3, 0], end = [1, 2, 3, 1]: the last cell says 1, but the answer is 3. Maximum Subarray Sum uses the same "best ending here" shape (Kadane's algorithm), with the same final maximum.

Cost. There are n states, and each scans up to n predecessors: O(n²) time and O(n) space. LeetCode allows n ≤ 2,500, so about 3.1 million inner iterations, which is fine. At n = 100,000 the same loop needs about 5 × 10⁹, which is not.

💡 When the rule names the predecessor. If the previous element must be exactly x - d (a fixed step), you don't need to scan every j. Keep a dictionary keyed by value, set best[x] = best.get(x - d, 0) + 1, and the whole pass takes expected O(n) time. The scan over all j is needed only when many earlier values could come before x.

Faster: keep the smallest tails

The O(n log n) method changes the notebook. Instead of one line per index, keep one line per length:

tails[k] = the smallest last value of any strictly increasing subsequence of length k + 1 seen so far.

Small tails are good, because they are the easiest to extend. For each new x, find the first tail that is >= x. If there is none, x extends the longest subsequence so far. Otherwise x replaces that tail with a smaller one.

bisect_left(tails, x) finds that position by binary search on the sorted list tails: it returns the first index whose value is >= x, in O(log n) time.

from bisect import bisect_left

def length_of_lis_fast(nums):
    tails = []      # tails[k] = smallest tail of any increasing subsequence of length k+1
    for x in nums:
        k = bisect_left(tails, x)   # first position whose tail is >= x
        if k == len(tails):
            tails.append(x)         # x extends the longest subsequence so far
        else:
            tails[k] = x            # x is a smaller tail for length k+1
    return len(tails)

The answer is len(tails), which is 4.

Why it works. The invariant: before each step, tails[k] is the smallest tail among all increasing subsequences of length k + 1 so far, and tails is strictly increasing. (It has to be: any subsequence of length k + 2 contains one of length k + 1 that ends at a smaller value.) A new x can extend exactly the lengths whose tails are smaller than x. The longest of those sits just before position k = bisect_left(tails, x), so x ends a subsequence of length k + 1. Because tails[k] >= x, x becomes the new smallest tail for that length, or the first tail of a new length if k == len(tails). No other length changes. As a bonus, k + 1 is the length of the longest increasing subsequence that ends exactly at x.

⚠️ tails need not be a subsequence. For [3, 4, 1] it ends as [1, 4], but the 1 comes after the 4 in the input. Only the length is guaranteed. To recover an actual subsequence, store each element's predecessor as you go.

⚠️ Strict or not. bisect_left gives strictly increasing subsequences: an equal x replaces the equal tail instead of extending it. For non-decreasing subsequences use bisect_right, which places an equal x after the equal tails. [2, 2, 2] gives 1 with bisect_left and 3 with bisect_right.

Cost. One binary search per element: O(n log n) time and O(n) extra space. For n = 100,000 that is about 1.7 million comparisons.

Your turn: run length_of_lis_fast by hand on [0, 8, 4, 12, 2, 10, 6, 14] and write tails after each element. Is the final tails a subsequence of the input this time?

Final round: no label on the problem

Real problems don't announce which sentence they want. Find the last decision, pick the index shape, then choose the operator.

Challenge 1: Delete and Earn

LeetCode 740: Delete and Earn. Pick any number x in nums to earn x points; every copy of x - 1 and x + 1 is then deleted. Repeat as often as you like. For [2, 2, 3, 3, 3, 4] the best is 9: pick the three 3s, which deletes both 2s and the 4. Values are between 1 and 10⁴.

def delete_and_earn(nums):
    if not nums:
        return 0
    points = [0] * (max(nums) + 1)
    for x in nums:
        points[x] += x          # taking value x earns x for every copy
    return rob(points)          # neighbouring values conflict, like neighbouring houses

Challenge 2: Perfect Squares

LeetCode 279: Perfect Squares. Return the fewest perfect squares (1, 4, 9, 16, …) that sum to n, for n ≤ 10⁴. For 12 the answer is 3 (4 + 4 + 4); for 13 it is 2 (4 + 9).

def num_squares(n):
    squares = [k * k for k in range(1, int(n ** 0.5) + 1)]
    return coin_change(squares, n)

Challenge 3: Combination Sum IV

LeetCode 377: Combination Sum IV. Given distinct positive nums and a target, count the ordered sequences of numbers from nums (reuse allowed) that sum to target. Despite the title, 1 + 2 and 2 + 1 count separately. For nums = [1, 2, 3] and target = 4 the answer is 7.

def combination_sum_4(nums, target):
    ways = [0] * (target + 1)
    ways[0] = 1
    for a in range(1, target + 1):       # amounts outside: order matters
        for x in nums:
            if x <= a:
                ways[a] += ways[a - x]
    return ways[target]

Boss level: Russian Doll Envelopes

LeetCode 354: Russian Doll Envelopes. Each envelope is [width, height], and one fits inside another only if both its width and its height are strictly smaller. What is the largest number of envelopes you can nest? For [[5, 4], [6, 4], [6, 7], [2, 3]] it is 3: [2, 3] inside [5, 4] inside [6, 7]. There can be up to 10⁵ envelopes.

def max_envelopes(envelopes):
    envelopes = sorted(envelopes, key=lambda e: (e[0], -e[1]))
    return length_of_lis_fast([h for _, h in envelopes])

Cheat sheet

Before moving on, pick one problem from this lesson and solve it aloud from a blank editor: the sentence for dp[i], the last decision and the cells it reads, the operator the question demands, the base cells the sentence implies, where the answer sits, and one input that breaks a tempting shortcut (greedy, end[-1], a missing guard, the wrong loop order). If you can do that for all five moves, a new 1D problem is mostly a search for the right sentence.

Next: 2D DP & Grid Problems for states that need two indices, such as grids and pairs of strings. Maximum Subarray Sum shows Kadane's algorithm, another "best ending here" DP.