1D DP

1D DP problems use a single array where dp[i] represents the optimal solution for the subproblem ending at index i.

Pattern 1: Fibonacci-like

Problems where each state depends on the previous one or two states.

// Template: dp[i] = dp[i-1] + dp[i-2]
// Example: Climbing Stairs, Fibonacci
public int solveFibonacci(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

Pattern 2: Maximum/Minimum Sum

Select elements to maximize/minimize sum with constraints.

// House Robber: Maximum sum of non-adjacent elements
// dp[i] = max value considering houses 0..i
public int rob(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1],      // Skip current house
                         dp[i - 2] + nums[i]);  // Rob current house
    }
    
    return dp[n - 1];
}

// Space-optimized version
public int robOptimized(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);
    
    for (int i = 2; i < n; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

Pattern 3: Kadane's Algorithm (Maximum Subarray)

// Maximum contiguous subarray sum
// dp[i] = max subarray sum ending at index i
public int maxSubArray(int[] nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        // Either extend previous subarray or start new one
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

Pattern 4: Decode Ways

// Count number of ways to decode a string of digits
// '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'
public int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;  // Empty string has 1 way
    dp[1] = s.charAt(0) != '0' ? 1 : 0;
    
    for (int i = 2; i <= n; i++) {
        // Single digit decode
        if (s.charAt(i - 1) != '0') {
            dp[i] += dp[i - 1];
        }
        
        // Two digit decode
        int twoDigit = Integer.parseInt(s.substring(i - 2, i));
        if (twoDigit >= 10 && twoDigit <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    
    return dp[n];
}

When to Use 1D DP

• Problem has sequential structure (array/string)
• State depends on a constant number of previous states
• You need to find optimal value (max/min/count)
• Greedy doesn't work (counterexample exists)

Why Optimize Space?

In many 1D DP problems, dp[i] only depends on a few previous values. We can reduce space from O(n) to O(1).

Observation

// If dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k])
// We only need to keep track of the last k values

Example: House Robber with O(1) Space

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

Generic Pattern for Rolling Variables

// Instead of:
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
    dp[i] = /* ... */;
}

// Use rolling variables:
int prev2 = baseValue1;
int prev1 = baseValue2;
for (int i = k; i <= n; i++) {
    int curr = /* depends on prev1, prev2, ... */;
    prev2 = prev1;
    prev1 = curr;
}
return prev1;  // or prev2 depending on the problem

Maximum Subarray with O(1) Space

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

Common Mistakes in Space Optimization

1. Forgetting base cases: Ensure initial values are correct
2. Overwriting values: Update in correct order
3. Wrong return value: Return the right variable (prev1 vs prev2)
4. Not handling n < k: When n is smaller than the number of variables needed