1D Dynamic Programming Pattern

The 1D Dynamic Programming pattern resolves linear optimization and counting problems by dividing them into overlapping subproblems, solving each subproblem once, and caching its result in a 1D state array (or rolling variables) to achieve linear time complexity.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks for the “maximum”, “minimum”, “longest”, or “number of ways” to complete a linear sequence.
• The state at the current index i depends directly on the solved states of recent indexes (e.g. i - 1, i - 2).
• The naive recursive solution has an exponential time complexity (O(2ⁿ)) due to resolving identical subproblem states.

How It Works

Instead of calculating subproblems repeatedly using recursion (which runs in O(2ⁿ)), you cache computed values:

• Top-Down (Memoization): Recursively solve the problem starting from the target, and store the result in a memoization array before returning.
• Bottom-Up (Tabulation): Initialize a 1D array of size n + 1 with base cases, and iterate forward, filling each index using a state transition equation.
• Space Optimization: If the current state only depends on a few previous states, you can replace the entire array with a few variables, reducing space from O(n) to O(1).

For example, to find the Nth Fibonacci number:

1. Base cases: dp[0] = 0, dp[1] = 1.
2. State transition: dp[i] = dp[i - 1] + dp[i - 2].
3. Space optimization: instead of an array, maintain prev2 = 0, prev1 = 1. In each step, compute curr = prev1 + prev2, then update prev2 = prev1 and prev1 = curr.

Complexity, With Caveats

• Time Complexity: O(n) where n is the size of the sequence. We evaluate each of the n states exactly once in constant time.
• Space Complexity: O(n) to store the 1D memoization or DP array. This can be optimized to O(1) space if the state transition only references a constant number of previous states (like the last two elements).

Minimal Code Template

public class DynamicProgramming1DTemplate {
    // Bottom-Up Tabulation (Climbing Stairs)
    public int climbStairs(int n) {
        if (n <= 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 1; // base cases
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // state transition
        }
        return dp[n];
    }

    // Space Optimized Bottom-Up (O(1) Space)
    public int climbStairsOptimized(int n) {
        if (n <= 1) return 1;

        int prev2 = 1;
        int prev1 = 1;

        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

# Bottom-Up Tabulation (Climbing Stairs)
def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1  # base cases
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # state transition

    return dp[n]


# Space Optimized Bottom-Up (O(1) Space)
def climb_stairs_optimized(n: int) -> int:
    if n <= 1:
        return 1

    prev2 = 1
    prev1 = 1

    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr

    return prev1

#include <vector>

class DynamicProgramming1DTemplate {
public:
    // Bottom-Up Tabulation (Climbing Stairs)
    int climbStairs(int n) {
        if (n <= 1) return 1;

        std::vector<int> dp(n + 1, 0);
        dp[0] = 1; // base cases
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // state transition
        }
        return dp[n];
    }

    // Space Optimized Bottom-Up (O(1) Space)
    int climbStairsOptimized(int n) {
        if (n <= 1) return 1;

        int prev2 = 1;
        int prev1 = 1;

        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

Where This Pattern Falls Short

• Lack of overlapping subproblems: If each path or state choice is completely unique (no subproblems overlap), dynamic programming behaves exactly like backtracking and adds memory overhead without any speed benefit.
• Non-subproblem dependencies: If the optimal choice at state i depends on the history of choices made to reach i rather than just the state value at i, the core assumption of dynamic programming (Bellman’s Principle of Optimality) is violated.

Related Patterns, Compared

• 2D Dynamic Programming: choose this instead when the state depends on two dimensions (e.g. grids, two string sequences, or range boundaries).
• Greedy: choose this instead when a local optimal choice is guaranteed to lead directly to the global optimal solution without needing to evaluate all subproblem paths (e.g. fractional knapsack).

Frequently Asked Questions

What is the difference between Tabulation and Memoization? Tabulation is a bottom-up approach that fills a table iteratively from base cases. Memoization is a top-down approach that uses recursion and caches results in a lookup table as they are computed.

How do you find the state transition equation? By starting with a small concrete example. Ask yourself: “If I already know the answers for sizes 1, 2, and 3, how can I use them to find the answer for size 4?”

What does this pattern test in interviews? It tests your ability to optimize exponential time complexity solutions to linear time, identify overlapping states, and apply space optimizations.