Linear DP

Problem

You are scanning a row (stairs, houses, digits, numbers) and each position offers a small set of choices that depend on only the last few positions. Brute force tries every combination of choices, which grows exponentially with length. A linear DP records, for each prefix, the one number that matters, and builds the next from the previous few.

Intuition

Standing on stair 7 you got there from stair 6 or from stair 5, and no other way. So the number of ways to reach 7 is the ways to reach 6 plus the ways to reach 5. Nothing about how you reached 6 changes what you can do next, which is exactly the "sufficient state" test from the fundamentals page. The table for 0 to 7 stairs is 1, 1, 2, 3, 5, 8, 13, 21: each entry is the sum of the two before it, so this is the Fibonacci sequence shifted by one place.

The skill is writing the recurrence from the last decision. Ask: how can the answer for the first i items end? Each different ending is one term, and what precedes it is a smaller instance of the same question, already in the table.

Blue bars are the houses the best plan takes. The green row is the table. The diagram scrolls sideways on a narrow screen.

Mechanics

The shape of every linear DP

1. dp[i] is the answer for the prefix of length i (or position i).
2. List the ways the prefix can end: the last step, the last item taken or skipped, the last one or two digits used.
3. Each way contributes dp[i - k] adjusted by that last choice. Combine with sum (counting), min or max (optimizing).
4. Seed the first one or two entries. Loop left to right. Keep only the last few entries if memory matters.

Take or skip

For the best total of non-adjacent values, best[i] = max(best[i - 1], best[i - 2] + nums[i]). Skipping house i leaves the best of the first i - 1 houses. Taking it means house i - 1 is unavailable, so you add to the best of the first i - 2. There are no other cases, so the maximum of the two is optimal. To recover which houses were taken, walk back: if best[i] equals best[i - 1], house i was skipped, otherwise it was taken and you jump two back.

Digit strings

To count ways to read digits as letters 1 to 26, the last letter is either the final digit (valid if it is not 0), which adds dp[i - 1], or the final two digits as a number from 10 to 26, which adds dp[i - 2]. A zero can never stand alone, so a "0" that cannot pair with the digit before it makes the count 0.

Products with negative numbers

The biggest product of a run ending at i is not determined by the biggest product ending at i - 1, because multiplying by a negative number reverses order. So carry two values: the biggest and the smallest product of runs ending here. For a new value x, both come from the three candidates x alone, biggest times x and smallest times x. The answer is the largest "biggest" seen.

The blue cell is the final answer. Notice the smallest column swings to -80 and then -240, while the biggest column reaches 24 on the last number.

Invariant

After processing position i, the stored value for i equals the true optimum over every choice sequence for the first i + 1 items. The proof is induction: every sequence ends in one of the listed ways, and for each way, the best completion uses an optimal prefix because the prefix and the last choice do not interact beyond the state.

Worked example

Climbing stairs. With 1 or 2 steps at a time, the ways to climb 0 to 7 stairs are 1, 1, 2, 3, 5, 8, 13, 21, so there are 21 ways to climb 7. The ways for 0 stairs is 1: do nothing.

Cheapest climb. If leaving stair i costs 4, 2, 9, 3, 6, 1 and you may start on stair 0 or 1, the cheapest cost to stand on positions 0 to 6 (the top) is 0, 0, 2, 2, 5, 5, 6. The answer is 6.

House robber. The houses are worth 4, 9, 3, 2, 8, 5. The table of best totals is 4, 9, 9, 11, 17, 17, so the answer is 17, from houses 1 and 4 (values 9 and 8). On a ring such as 5, 1, 2, 1, 5 the first and last are neighbours: skipping the last gives 7, skipping the first gives 7, so the answer is 7, against 12 on a straight line.

Decode ways. For the digits 2261 the table of counts for each prefix length is 1, 1, 2, 3, 3, giving 3 readings. For "1001" the answer is 0, because the "00" cannot be read.

Maximum product. On 2, -5, -2, -4, 3 the answer is 24, the run from the third number to the end. A version that kept only the biggest product would have missed it, since the number that makes it needs the smallest one first.

Implementation

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


def rob(nums):
    skip = take = 0               # best without / with the previous house
    for value in nums:
        skip, take = max(skip, take), skip + value
    return max(skip, take)


def num_decodings(s):
    prev, cur = 1, 1 if s and s[0] != "0" else 0   # dp[i-2], dp[i-1]
    for i in range(2, len(s) + 1):
        ways = cur if s[i - 1] != "0" else 0
        if 10 <= int(s[i - 2:i]) <= 26:
            ways += prev
        prev, cur = cur, ways
    return cur if s else 0


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

Variations and edge cases

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


def min_cost_climbing(cost):
    a = b = 0
    for i in range(2, len(cost) + 1):
        a, b = b, min(b + cost[i - 1], a + cost[i - 2])
    return b


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


def integer_break(n):
    best = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        best[i] = max(max(j * (i - j), j * best[i - j]) for j in range(1, i))
    return best[n]


def stone_game_iii(values):
    n = len(values)
    diff = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        diff[i] = max(sum(values[i:i + k]) - diff[i + k] for k in (1, 2, 3) if i + k <= n)
    return diff[0]

• Ring. Run the line version twice, once without the first and once without the last; the single-element case needs its own return.
• Longer steps. If you can climb 1, 2 or 3 stairs, the recurrence sums three previous entries. Tribonacci for 0 to 10 is 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149.
• Splitting a number. Breaking 10 into at least two positive parts to maximize the product has table 0, 1, 1, 2, 4, 6, 9, 12, 18, 27, 36 and answer 36 (3 + 3 + 4). Each part may stay whole or be split again.
• Game DP. Store the mover's lead. Moving takes some stones and then it is the opponent's turn with their lead subtracted. For the row 3, -4, 5, 6, -2 the first player's lead is -4, so the second player wins.
• Zeros. In decode ways, a lone 0 contributes nothing and 10 or 20 can only be read as a pair. Handle both before adding.
• Edge cases: empty input, a single element, all negative numbers (the product answer is the largest single number), and a prefix of length one that needs its own base case.

Complexity and tradeoffs

• Time: O(n) for a constant number of earlier entries. Integer break is O(n²) as written, since each entry looks at O(n) split points; Stone Game III stays O(n), since each entry tries at most three moves.
• Space: O(n) for a table, O(1) with rolling variables when only the last few entries are read.
• Baseline. Plain recursion branches by the number of choices at every position: about 1.6 to the n for stairs, 2 to the n for take-or-skip.
• When it fails. If a choice depends on something not in the prefix index (a remaining budget, a pair of positions) the state needs another dimension: knapsack or grid DP. If a greedy rule is provable, as for maximum subarray sum, a single running value replaces the table.

Problems

Climbing Stairs, Min Cost Climbing Stairs and N-th Tribonacci Number are the pure sum or min of the last one to three entries. House Robber and its ring version use take-or-skip. Decode Ways adds conditional terms. Maximum Product Subarray needs the second, smallest track. Integer Break and Stone Game III show that the same shape covers splitting and two-player questions.

Easy

• 70. Climbing Stairs Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The ways to reach step n are the ways to reach n-1 plus n-2, the Fibonacci recurrence with two variables.
• 746. Min Cost Climbing Stairs NeetCode 150 NeetCode 250
  The cheapest way to stand on a step is its cost plus the cheaper of the two steps below, ending past the top.
• 1137. N-th Tribonacci Number NeetCode 250
  Keep the last three values and slide them forward, the same idea as Fibonacci with one more term.

Medium

• 91. Decode Ways Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The decodings of a prefix come from the prefix one shorter if the last digit is valid and two shorter if the last two digits are.
• 152. Maximum Product Subarray Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Track both the largest and the smallest product ending at each index, since a negative number swaps their roles.
• 198. House Robber Blind 75 Grind 169 NeetCode 150 NeetCode 250
  At each house take the better of skipping it or robbing it plus the best total from two houses back.
• 213. House Robber II Blind 75 NeetCode 150 NeetCode 250
  The houses form a circle, so run the straight-line robber twice, once without the first house and once without the last.
• 343. Integer Break NeetCode 250
  The best product for n is the best over first-piece lengths of that piece times the better of the remainder kept whole or broken further.

Hard

• 1406. Stone Game III NeetCode 250
  Let a value be the best score difference the current player can force from index i, trying one, two or three stones.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 338. Counting Bits Easy
• 53. Maximum Subarray Medium
• 55. Jump Game Medium
• 337. House Robber III Medium
• 377. Combination Sum IV Medium
• 978. Longest Turbulent Subarray Medium
• 2707. Extra Characters in a String Medium

Connections

Linear DP is the one-dimensional case of the knapsack, grid and string tables to come: add a second index and the same recipe applies. Maximum Subarray is its simplest relative, where the running value collapses to a single number (Kadane's algorithm), and House Robber III applies the take-or-skip idea to trees.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14 (dynamic programming), including the rod-cutting recurrence.
• Skiena, The Algorithm Design Manual, chapter 10 (dynamic programming), on counting Fibonacci-style recurrences.
• Sedgewick and Wayne, Algorithms, section 1.1 (recursion) and section 4.4 (acyclic shortest paths), where relaxing vertices in topological order is a bottom-up DP.
• Bellman, Dynamic Programming, Princeton University Press, 1957.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.