1D Dynamic Programming

1. Introduction: Those Who Cannot Remember the Past

Imagine you need to calculate the 100th Fibonacci number. You calculate F(99) + F(98). But to calculate F(99), you calculate F(98) + F(97). Notice that you are calculating F(98) twice. And you will calculate F(97) three times. By the time you get to F(2), you will have calculated it trillions of times!

Dynamic Programming (DP) is a mathematical optimization technique based on a very simple quote: "Those who cannot remember the past are condemned to repeat it."

Whenever a recursive algorithm solves the exact same subproblem multiple times, we can cache (save) the result of that subproblem in an array or HashMap. The next time we need the answer, we look it up in $O(1)$ time instead of recalculating it. 1D DP specifically refers to problems where the state can be represented by a single integer (usually an index or a target sum), meaning our cache is just a 1-Dimensional array.

2. Core Concept: Memoization vs Tabulation

There are two ways to implement DP. They both achieve the exact same time complexity, but approach the problem from different directions.

1. Top-Down (Memoization): You write a standard recursive function. At the start of the function, you check an array cache[n]. If it has a value, return it. If not, calculate it, save it to cache[n], and then return it. It is "Top-Down" because you start at the target $N$ and work down to the base cases.
2. Bottom-Up (Tabulation): You abandon recursion entirely. You create an array dp[]. You manually fill in the base cases dp[0] and dp[1]. Then, you use a for loop to build the answers up to $N$. It is "Bottom-Up" because you start at 0 and build up to the target.

In technical interviews, Bottom-Up is highly preferred because it avoids the overhead (and potential StackOverflows) of recursion.

3. Beginner Code Example: Climbing Stairs

Problem Statement: (LeetCode 70) You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

The Insight: To reach step i, you must have come from either step i-1 (by taking a 1-step) or step i-2 (by taking a 2-step). Therefore, the total ways to reach step i is simply ways(i-1) + ways(i-2). This is literally the Fibonacci sequence!

Bottom-Up DP

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (n <= 2) return n;
        
        // 1. Create the DP array
        int[] dp = new int[n + 1];
        
        // 2. Initialize Base Cases
        dp[1] = 1; // 1 way to reach step 1
        dp[2] = 2; // 2 ways to reach step 2 (1+1, or 2)
        
        // 3. Build up the table
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

Space Optimization: Notice that dp[i] only relies on the two previous steps. We don't need a whole array!

public static int climbStairsOptimized(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2, current = 0;
    for (int i = 3; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

Complexity: Time $O(N)$. Space $O(1)$.

4. Intermediate Code Example: House Robber

Problem Statement: (LeetCode 198) You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected. You cannot rob two adjacent houses. Find the maximum money you can rob.

The DP State Relation: At any house i, you have two choices:

1. Rob it: You get nums[i], but you CANNOT rob house i-1. So your total is nums[i] + dp[i-2].
2. Skip it: You get no money from house i, but you keep the max money up to house i-1. So your total is dp[i-1]. You naturally want the maximum of these two choices! dp[i] = max(nums[i] + dp[i-2], dp[i-1])

public class HouseRobber {
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int[] dp = new int[nums.length];
        
        // Base cases
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // Build the table
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }
        
        return dp[nums.length - 1];
    }
}

5. Advanced Code Example: Longest Increasing Subsequence (LIS)

Problem Statement: (LeetCode 300) Given an integer array nums, return the length of the longest strictly increasing subsequence. (A subsequence is derived by deleting some or no elements without changing the order of the remaining elements).

The Insight: Let dp[i] be the length of the LIS that strictly ends at index i. To find dp[i], we look at all previous indices j (where j < i). If nums[i] > nums[j], it means we can append nums[i] to the LIS that ended at j. So, dp[i] = max(dp[i], dp[j] + 1).

import java.util.Arrays;

public class LIS {
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // dp[i] represents the LIS ending at index i
        int[] dp = new int[nums.length];
        
        // Every single element is an increasing subsequence of length 1 by itself
        Arrays.fill(dp, 1);
        
        int maxLength = 1;
        
        // For every element i...
        for (int i = 1; i < nums.length; i++) {
            // Look back at every previous element j...
            for (int j = 0; j < i; j++) {
                // If it's strictly increasing, we can extend the sequence!
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // Keep track of the global maximum LIS found
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
}

Complexity Analysis:

• Time Complexity: $O(N^2)$. The nested loops compare every pair. (Note: There is an advanced $O(N \log N)$ solution using Binary Search + DP, but the $O(N^2)$ solution is the core standard for DP interviews).
• Space Complexity: $O(N)$ for the dp array.

6. Common Mistakes Beginners Make

1. Not defining the state clearly

   • The Mistake: Just making an array dp[] and guessing what the math should be.
   • Why it's wrong: You will get lost instantly. You MUST be able to write down a plain English sentence defining the array. Example: "dp[i] is the maximum money I can rob from house 0 up to house i." If you can't state this clearly, you can't write the formula.

2. Index Out of Bounds on Base Cases

   • The Mistake: Writing dp[1] = nums[1]; without checking if (nums.length == 1) return nums[0];.
   • Why it's wrong: If the input array only has 1 item, trying to set dp[1] will throw an exception. Always handle small edge-case inputs at the very top of your DP function.

3. Thinking Greedy is DP

   • The Mistake: In Coin Change, always picking the largest coin first. (e.g., Target 14, Coins [10, 7, 1]. Greedy picks 10, then four 1s. Total 5 coins. The optimal DP answer is two 7s. Total 2 coins!).
   • The Fix: Never assume a local greedy choice leads to the global optimum unless you can mathematically prove it. DP explores all mathematically viable paths safely.

7. Interview Q&A

Q1: How do I know when a problem requires Dynamic Programming? Answer: Look for two properties:

1. Overlapping Subproblems: You can break the problem into smaller problems, and those smaller problems repeat (like Fibonacci).
2. Optimal Substructure: The optimal solution to the big problem can be built directly from the optimal solutions of the smaller problems. (e.g., The best way to reach step 10 is built from the best way to reach step 9).

Q2: Should I use Memoization (Top-Down) or Tabulation (Bottom-Up)? Answer: Start by writing the Top-Down recursion on a whiteboard to prove you understand the logic. Then, say to the interviewer: "Recursion takes $O(N)$ memory on the call stack and has overhead. I will now write this Bottom-Up iteratively for optimal performance."

Q3: (LeetCode 322) Coin Change: How do you represent an invalid state? Answer: If a target sum cannot be made with the given coins, we shouldn't store 0 because 0 coins is the answer for a target of 0. Instead, initialize the DP array with amount + 1 (acting as Infinity). If the final answer is still amount + 1, return -1.

8. Practice Problems

1. Min Cost Climbing Stairs (LeetCode 746)
   • Goal: Similar to Climbing Stairs, but now each step costs money.
2. Coin Change (LeetCode 322)
   • Hint: dp[amount] = min(dp[amount], dp[amount - coin] + 1).
3. Decode Ways (LeetCode 91)
   • Hint: A string parsing problem that is secretly exactly the same logic as Climbing Stairs! (A letter is either 1 digit or 2 digits long).

9. Summary

• The Formula: State Definition + Base Cases + Transition Equation.
• Top-Down vs Bottom-Up: Top-Down uses recursion + caching. Bottom-Up uses loops + an array. Bottom-up is preferred.
• State Optimization: If dp[i] only ever looks at dp[i-1] and dp[i-2], you do not need an $O(N)$ array. You only need two variables, achieving $O(1)$ space.
• Identify DP: Look for keywords like "maximum/minimum", "number of ways", and problems involving making sequential choices (robbing, climbing, choosing coins).