1-D Dynamic Programming

At a glance

The instinct

When a problem walks along a single sequence (stairs, houses, days, characters) and asks for a count, a minimum or a maximum, try to answer "what is the best I can do ending at (or up to) position i?" If that answer can be built from the answers at i-1 and i-2 (or a few more), you have 1-D DP. Brute-force recursion explores the same suffixes over and over; storing each position's answer once turns an exponential tree into a straight line.

The gateway examples are Climbing Stairs (Fibonacci in disguise) and House Robber (take this house and jump two, or skip it).

Recognise it

Not this pattern if...

• A greedy choice is provably optimal (e.g., Jump Game reachability): DP works but is overkill.
• The answer at i depends on all earlier j with a comparison (that is the LIS pattern) or on a capacity/target (that is knapsack).
• Two sequences or two indices are involved: you need a 2-D table (string DP, grid DP).

Memory hack

Analogy: you are climbing stairs in the dark with a notebook. On each stair you write one number - the best result for reaching this stair - computed only from what you wrote on the last one or two stairs. You never need to flip back further, so a sticky note with two numbers is enough.

Say it out loud in the interview:

1. "dp[i] means the best answer for the first i items / ending at i."
2. "At i I can either take it or skip it (or step from i-1 / i-2), so dp[i] = combine(those)."
3. "Base cases are dp[0] and dp[1]; I fill left to right, and since I only look back two, I can keep two variables."

How it works

Define the state precisely, write the recurrence, seed the base cases, and loop in an order where every dependency is already computed. For House Robber, dp[i] = most money from the first i houses. At house i you either skip it (keep dp[i-1]) or rob it (dp[i-2] + nums[i-1]).

Trace on nums = [2, 7, 9, 3, 1]:

Only the two most recent dp values are ever read, so prev2, prev1 replace the array. A good workflow in interviews: recursion → memoisation → bottom-up table → rolling variables, saying out loud why each step is safe.

Java template

import java.util.*;

class OneDimensionalDP {
    // Bottom-up with a full table: easiest to get right first.
    static int solveTable(int[] a) {
        int n = a.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;                                    // base case: nothing chosen
        if (n >= 1) dp[1] = a[0];                     // base case: first element
        for (int i = 2; i <= n; i++) {
            // choice: skip a[i-1]  vs  take a[i-1] and jump back two
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i - 1]);
        }
        return dp[n];
    }

    // Same recurrence with O(1) space: roll the last two answers.
    static int solveRolling(int[] a, int from, int to) {   // inclusive range, handy for circular variants
        int prev2 = 0, prev1 = 0;
        for (int i = from; i <= to; i++) {
            int cur = Math.max(prev1, prev2 + a[i]);  // replace with problem-specific combine
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }

    // Circular array: the first and last items cannot both be used.
    static int solveCircular(int[] a) {
        int n = a.length;
        if (n == 1) return a[0];
        return Math.max(solveRolling(a, 0, n - 2), solveRolling(a, 1, n - 1));
    }

    // Top-down memo: write this first if the recurrence is unclear.
    static int ways(int i, int[] memo) {
        if (i <= 1) return 1;                         // base: one way to stand at step 0 or 1
        if (memo[i] != 0) return memo[i];
        return memo[i] = ways(i - 1, memo) + ways(i - 2, memo);
    }
}

Complexity

• Time: O(n × k), where k is how many earlier positions each step looks at - O(n) for the classic two-lookback problems.
• Space: O(n) for the table or memo; O(1) after rolling to k variables. The recursive memo also uses O(n) call stack, which can overflow for n around 10⁵ in Java, so prefer bottom-up there.

Variations

• Counting ways: Climbing Stairs - dp[i] = dp[i-1] + dp[i-2]; with steps from a set S, sum over S.
• Min cost with lookback: Min Cost Climbing Stairs - dp[i] = cost[i] + min(dp[i-1], dp[i-2]); the answer is the cheaper of the last two.
• Take or skip (no adjacent): House Robber; Delete and Earn reduces to it after bucketing values.
• Circular constraint: House Robber II - solve two linear ranges and take the max.
• Ending-here DP: Maximum Subarray and Maximum Product Subarray - track the best run ending at i (for products, track both max and min, since a negative flips them).
• State machine per index: Best Time to Buy and Sell Stock with Cooldown - a few variables (hold, sold, rest) updated together each day.
• Prefix decoding: Decode Ways - a single-string cousin where dp[i] reads one or two characters back; covered in String DP.

Common mistakes

• Vague state. "dp[i] is the answer" is not enough - say whether it covers the first i items or ends exactly at i; the recurrence and final answer differ.
• Off-by-one base cases. Decide whether dp is indexed by items (size n + 1) or positions (size n) and stay consistent.
• Forgetting tiny inputs. n = 0, n = 1 and, for the circular version, n = 1 need explicit handling.
• Greedy temptation. Picking the larger of neighbouring houses locally fails on inputs like [2, 1, 1, 2].
• Deep recursion in Java. Top-down memo on large n can throw StackOverflowError; convert to a loop.

All practice problems

4 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.