Linear 1D DP

You are standing at the bottom of a staircase with n steps. You can climb one step or two steps at a time. How many distinct ways can you reach the top?

If you have never seen dynamic programming before, your first instinct might be to try every possible combination of 1-steps and 2-steps. That works, but it is painfully slow: the number of paths grows exponentially. There is a much better way, and understanding it will unlock an entire family of problems. The key observation is that to reach step i, you must have come from either step i-1 (taking a single step) or step i-2 (taking a double step). So the number of ways to reach step i is the number of ways to reach step i-1 plus the number of ways to reach step i-2. That's it. That is the entire algorithm.

This is linear 1D dynamic programming, probably the most common DP pattern you will encounter in interviews. "Linear" because you sweep through a sequence from left to right. "1D" because your state is a single index. Once you can see this pattern, you will recognize it everywhere.

The core idea

Every linear 1D DP problem has the same skeleton. You define an array dp where dp[i] represents the answer to the problem considering only the first i elements. Then you fill it in from left to right using a recurrence relation, a formula that computes dp[i] from earlier entries, usually dp[i-1] and dp[i-2].

What varies from problem to problem is three things: what dp[i] means, what the recurrence is, and what operator you use to combine subproblems. For counting problems (like climbing stairs), you add. For optimization problems (like house robber), you take a max or min. Getting the operator wrong is a surprisingly common bug: the code compiles and runs, but the answer is silently wrong.

Let's make this concrete with two classic examples.

Climbing stairs

LeetCode 70 captures this directly. The state definition is: dp[i] = the number of distinct ways to reach step i.

The recurrence is: dp[i] = dp[i-1] + dp[i-2]. You can arrive at step i from one step below or two steps below, and these paths are disjoint, so you add.

The base cases are: dp[0] = 1 (one way to be at the ground, do nothing) and dp[1] = 1 (one way to reach step 1, take one step).

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

If you recognize this recurrence, it is the Fibonacci sequence. That is not a coincidence: Fibonacci is the simplest possible linear DP.

House robber

Consider LeetCode 198: you are a robber planning to rob houses along a street. Each house has a certain amount of money, but you cannot rob two adjacent houses (the alarm system will go off). What is the maximum money you can rob?

The state definition is: dp[i] = the maximum money you can rob from houses 0 through i.

The recurrence requires you to make a choice at each house: rob it, or skip it. If you rob house i, you gain nums[i] but must skip house i-1, so the best you can do from the earlier houses is dp[i-2]. If you skip house i, your total is just dp[i-1]. You want the better option: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Notice the operator is now max instead of +. This is an optimization problem, not a counting problem.

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

The space optimization

Look at the two solutions above. In both cases, dp[i] only depends on dp[i-1] and dp[i-2]. We are maintaining an entire array, but at any point we only ever look back two positions. This means we can throw away the array entirely and just keep two variables.

def rob(nums):
    if not nums:
        return 0
    prev2, prev1 = 0, 0
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = curr
    return prev1

This takes $O(1)$ space instead of $O(n)$. In an interview, you should almost always present the space-optimized version. It shows you understand what the DP is actually doing, not just that you can fill in a table.

The variable names prev2 and prev1 are a convention: prev1 is the answer for "everything up to the previous element," and prev2 is the answer for "everything up to two elements ago." After computing the current value, you shift the window forward. The order matters. If you update prev1 before computing curr, you lose the old value of prev1 that you needed.

Decode Ways

LeetCode 91. Decode Ways asks: given a string of digits like "226", how many ways can you decode it into letters, where 'A' = 1, 'B' = 2, ..., 'Z' = 26? For "226", the answer is 3: "BZ" (2, 26), "VF" (22, 6), or "BBF" (2, 2, 6).

The state definition is: dp[i] = the number of ways to decode the first i characters.

The recurrence has two cases. If the single digit s[i-1] is between '1' and '9', it is a valid one-character decoding, so add dp[i-1]. If the two-digit number formed by s[i-2:i] is between 10 and 26, it is a valid two-character decoding, so add dp[i-2]. The key difference from Climbing Stairs is that not every transition is valid. A '0' cannot be decoded on its own, and "37" is not a valid two-digit code.

def numDecodings(s):
    if not s or s[0] == '0':
        return 0
    n = len(s)
    prev2, prev1 = 1, 1  # dp[0] = 1, dp[1] = 1
    for i in range(2, n + 1):
        curr = 0
        if s[i - 1] != '0':
            curr += prev1
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            curr += prev2
        prev2 = prev1
        prev1 = curr
    return prev1

This is a great example of how linear 1D DP adapts to constraints. The skeleton is the same as Climbing Stairs, looking back one and two steps, but each transition is conditionally valid.

Min Cost Climbing Stairs

LeetCode 746. Min Cost Climbing Stairs gives you an array cost where cost[i] is the cost of stepping on stair i. You can start from step 0 or step 1 and climb one or two steps at a time. Find the minimum cost to reach the top (past the last step).

The state definition is: dp[i] = the minimum cost to reach step i. The recurrence is: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). You pay the cost of the current step plus the cheaper of the two ways to get here. The answer is min(dp[n-1], dp[n-2]) since you can jump past the last step from either of the final two positions.

def minCostClimbingStairs(cost):
    prev2, prev1 = cost[0], cost[1]
    for i in range(2, len(cost)):
        curr = cost[i] + min(prev1, prev2)
        prev2 = prev1
        prev1 = curr
    return min(prev2, prev1)

Notice how this is an optimization problem (using min) rather than a counting problem (using +). The skeleton is identical to House Robber. The only difference is the recurrence formula.

How to recognize this pattern

When you see a new problem, ask yourself these questions:

Am I making a sequential decision at each position in an array or sequence? Does the decision at position i depend only on a fixed, small number of previous positions, not on all of them, and not on future positions? Am I looking for an optimal value (max, min) or a count of ways?

If the answer to all three is yes, you are almost certainly looking at linear 1D DP. Here are some of the classic problems in this family: Climbing Stairs, House Robber, Min Cost Climbing Stairs, Decode Ways, Maximum Alternating Subsequence Sum, Delete and Earn, and Paint House.

A subtlety: what linear 1D DP is not

Some problems look like they belong here but actually have a different structure. Coin Change asks for the minimum number of coins to make a target amount, and it tempts you into writing a simple left-to-right recurrence. But the coins can be reused, and the state dimension is the target amount rather than the position in an array. It is an unbounded knapsack problem, not linear DP. The tell is that the "previous positions" you depend on are not a fixed window but depend on the coin values.

Similarly, Word Break looks like it should be dp[i] = dp[i-1] or dp[i-2], but you actually need to check all possible word endings at each position, making it $O(n \cdot m)$ where m depends on the dictionary. If the set of "previous positions" is variable or data-dependent rather than a fixed constant like 1 or 2, you have left the linear DP pattern and entered something more complex.

Complexity

Time is always $O(n)$: you visit each element once and do constant work per element. Space is $O(1)$ with the rolling-variable optimization, or $O(n)$ if you keep the full table. You might keep the full table during debugging (it is easier to print and inspect), then optimize to $O(1)$ once the logic is correct.

Putting it all together

The recipe for any linear 1D DP problem is mechanical once you have practiced it a few times:

1. Define the state: what does dp[i] represent?
2. Find the recurrence: how does dp[i] relate to dp[i-1], dp[i-2], etc.?
3. Set the base cases: what are dp[0] and dp[1]?
4. Choose the operator: are you adding (counting) or taking max/min (optimizing)?
5. Iterate left to right, filling in the table.
6. Optimize space by replacing the array with rolling variables.

The hard part is step 1. Once you have the right state definition, everything else follows. If you are stuck, try writing out a few examples by hand. Draw the table. See which earlier entries each cell depends on. The pattern will reveal itself.

Recognizing this pattern

You're probably looking at linear 1D DP when:

• The input is a single sequence (array or string) and the answer accumulates as you sweep left to right.
• The decision at index i depends on a fixed, constant number of earlier indices, usually i-1 and i-2, occasionally i-k for small constant k.
• The problem asks for a count of ways, a maximum/minimum total, or a yes/no reachability over the prefix.
• Constraints are large enough ($n \le 10^5$ or higher) that an $O(n^2)$ scan-everything-behind approach would time out.

Common templates:

• Fibonacci-style counting: dp[i] = dp[i-1] + dp[i-2] for paths/ways. Example: Climbing Stairs.
• Take-or-skip optimization: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) when adjacent picks conflict. Example: House Robber.
• Conditional transition: same skeleton as Fibonacci but each lookback only contributes if a validity check passes. Example: Decode Ways.
• Min-cost prefix: dp[i] = cost[i] + min(dp[i-1], dp[i-2]) for cheapest way to land at i. Example: Min Cost Climbing Stairs.
• Multi-state per index: track a small tuple (e.g. paint-house color, last-action flag) at each i instead of a scalar. Example: Paint House.