1D DP

One-dimensional DP uses a state that depends on one index (or one “dimension”) such as dp[i]. It is the most common entry point to dynamic programming and appears in a huge number of interview problems. This article walks you through when to use it, how to define state and transitions, and how to implement and optimize 1D DP solutions.

When to Use 1D DP

You typically use 1D DP when:

The problem is defined on a single sequence (array or string) or on a single numeric parameter (e.g. amount, capacity, steps).
The optimal answer for a given position (or value) can be expressed in terms of smaller indices or smaller values only.
You need one recurring quantity per position: “best value for prefix [0..i]”, “number of ways to reach i”, “min cost to achieve i”, etc.

If the subproblem naturally needs two independent indices (e.g. two positions in two strings, or row and column in a grid), you are in 2D DP territory instead.

State Definition: What Does dp[i] Mean?

The single most important step is to define what dp[i] represents. The definition must be:

Unambiguous: one clear meaning (e.g. “max profit from days 0..i including day i” vs “excluding day i”).
Sufficient: you can write a recurrence using only “smaller” states.
Aligned with the problem: the final answer is either some dp[i] or a simple combination (e.g. max(dp[0], …, dp[n-1])).

Common 1D state meanings:

State meaning	Example
Answer for prefix `[0..i]` (including `i`)	Max sum subarray ending at `i`, LIS length ending at `i`
Answer for prefix `[0..i]` (choice at `i`: take or skip)	House Robber, Climbing Stairs
Answer for value `i` (e.g. amount, capacity)	Min coins to make amount `i`, max value for capacity `i`
Number of ways to reach `i`	Climbing Stairs, Decode Ways

Once the state is fixed, the transition and base cases follow.

Pattern 1: Linear Recurrence (Fibonacci Family)

The simplest 1D pattern is a recurrence that only looks back a fixed number of steps.

Climbing Stairs: You can climb 1 or 2 steps. How many distinct ways to reach step n?

State: dp[i] = number of distinct ways to reach step i.
Transition: To reach i, you came from i-1 (one step) or i-2 (two steps):
- dp[i] = dp[i-1] + dp[i-2].
Base: dp[0] = 1 (one way: stay at ground), dp[1] = 1.
Answer: dp[n].

Java
public int climbStairs(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Space is optimized to O(1) because each step only needs the previous two values. This is the same recurrence as Fibonacci.

General idea: If your recurrence only uses dp[i-1], dp[i-2], … up to a constant number of indices, you can always reduce space to O(1) with a few variables.

Pattern 2: Choice-Based (Take or Skip)

Many problems give a choice at each index: take the current element (with some rule) or skip it. The state is usually “best answer for prefix [0..i]” and the transition considers both options.

House Robber (simplified): You cannot rob two adjacent houses. Maximize total money.

State: dp[i] = maximum money we can rob from houses [0..i] (we may or may not rob i).
Transition:
- Rob house i: then we cannot rob i-1, so value = nums[i] + dp[i-2].
- Skip house i: value = dp[i-1].
- So dp[i] = max(dp[i-1], nums[i] + dp[i-2]).
Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
Answer: dp[n-1].

Java
public int rob(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    int prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int cur = Math.max(prev1, nums[i] + prev2);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Again, only the last two values are needed, so O(1) space.

Takeaway: For “take or skip” with a small dependency window (e.g. cannot take adjacent), state = “best for prefix”, transition = max/min over a few previous states.

Pattern 3: Prefix/Suffix “Ending at i”

Sometimes the natural state is “best (or count of) something that ends exactly at index i”. The final answer is then the best (or sum) over all i.

Maximum Subarray (Kadane): Find the contiguous subarray with the largest sum.

State: dp[i] = maximum sum of a contiguous subarray that ends at index i (must include nums[i]).
Transition: Either extend the best subarray ending at i-1, or start fresh at i:
- dp[i] = nums[i] + max(0, dp[i-1]).
Base: dp[0] = nums[0].
Answer: max(dp[0], dp[1], …, dp[n-1]). In code we usually keep a running max.

Java
public int maxSubArray(int[] nums) {
    int n = nums.length;
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < n; i++) {
        cur = nums[i] + Math.max(0, cur);
        best = Math.max(best, cur);
    }
    return best;
}

Longest Increasing Subsequence (LIS): Length of the longest strictly increasing subsequence (not necessarily contiguous).

State: dp[i] = length of the LIS ending at index i (must include nums[i]).
Transition: We can extend any smaller j < i with nums[j] < nums[i]:
- dp[i] = 1 + max{ dp[j] : j < i and nums[j] < nums[i] }, or 1 if no such j.
Base: dp[i] = 1 for all i (at least the element itself).
Answer: max(dp[0], …, dp[n-1]).

This is O(n²) with a single array. Note: LIS can be solved in O(n log n) with binary search, but the DP definition is still important to understand.

Java
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    int best = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], 1 + dp[j]);
            }
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

Takeaway: “Ending at i” states often require scanning all smaller indices; the recurrence is 1D but each step may take O(n), giving O(n²) total.

Pattern 4: Single Numeric Parameter (Amount, Capacity)

Here the index is not an array position but a value: amount of money, capacity of a knapsack, etc. The state is dp[v] = best answer when the parameter equals v.

Coin Change (minimum number of coins): Given coin denominations and a target amount, find the minimum number of coins needed to make that amount (or -1 if impossible).

State: dp[a] = minimum number of coins needed to make amount a.
Transition: For each coin c, if a >= c we can use one coin of value c and then solve for a - c:
- dp[a] = 1 + min{ dp[a - c] : c in coins and a >= c }.
- If no coin can be used, treat as impossible (e.g. infinity).
Base: dp[0] = 0 (no coins needed for amount 0).
Answer: dp[amount], or -1 if it remains impossible.

Java
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // sentinel for "impossible"
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) {
                dp[a] = Math.min(dp[a], 1 + dp[a - c]);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Iteration order: we fill dp from 0 to amount so that when we compute dp[a], all dp[a - c] are already computed.

Takeaway: When the “index” is a value (amount, capacity), the recurrence is still 1D; iterate over that value in increasing order and ensure dependencies are ready.

Base Cases and Iteration Order

Base cases are the smallest subproblems (e.g. empty prefix, amount 0). Set them explicitly so the recurrence never reads undefined or wrong values.
Iteration order in bottom-up 1D DP is almost always forward: from i = 0 (or 1) to n. That way when you compute dp[i], all dp[j] for j < i are already computed.
Exception: if your recurrence uses dp[i + 1] (e.g. “depends on the future”), iterate backward so that i+1 is ready before i.

Space Optimization in 1D DP

Many 1D recurrences only depend on a bounded window of previous values (e.g. last one or two). Then you can:

Replace dp[] with a few variables (e.g. prev2, prev1, cur) and roll them in a loop.
This reduces space from O(n) to O(1).

Always check: “Which previous indices does dp[i] depend on?” If it’s a constant number, rolling variables are enough.

Summary Table: Classic 1D DP Problems

Problem	State	Transition idea	Order
Climbing Stairs	ways to reach step i	dp[i-1] + dp[i-2]	forward
House Robber	max profit from [0..i]	max(skip, take + dp[i-2])	forward
Maximum Subarray	max sum ending at i	nums[i] + max(0, dp[i-1])	forward
LIS	LIS length ending at i	1 + max dp[j] for j<i, nums[j]<nums[i]	forward
Coin Change	min coins for amount a	1 + min dp[a-c] over coins c	forward (a from 0 to amount)

Practice Tips

Always write the state definition in one sentence before coding.
Write the recurrence in math (or pseudocode) and check base cases on a tiny example.
Implement bottom-up with a 1D array first; then optimize space if the dependency window is small.
For “ending at i” problems, remember the answer is often max(dp) or min(dp), not necessarily dp[n-1].

Once you are comfortable with 1D state, transitions, and iteration order, you can extend the same discipline to 2D DP (two indices or two dimensions).