1D Dynamic Programming: Climbing Stairs & House Robber

The 1D DP Problem-Solving Pattern

As a quick recap, our general strategy for these problems will be:

1. Understand the Problem & Choices: Break down the problem. At any given point (e.g., at step i or house i), what are the possible decisions?
2. Define the State & Recurrence Relation: Define what dp[i] will represent. Usually, it's the answer to the subproblem for the first i elements. Then, formulate the recurrence relation that connects dp[i] to previous states (e.g., dp[i-1], dp[i-2]).
3. Identify Base Cases: Determine the solutions for the smallest subproblems (e.g., dp[0], dp[1]) that don't depend on any others.
4. Implement Bottom-Up (Tabulation): Write a loop that builds your dp table from the base cases up to the final answer.
5. Optimize for Space: Check if the recurrence for dp[i] only depends on a fixed number of previous states. If so, replace the dp array with a few variables to reduce space complexity, typically from O(n) to O(1).

Let's apply this pattern.

Problem 1: Climbing Stairs (LeetCode 70)

This problem is a classic introduction to DP and is functionally identical to the Fibonacci sequence we've discussed.

The Problem: 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?

Let's break this down using our pattern.

Step 1: Understanding the Choices

To reach the n-th step, what was your last move? You must have come from either:

• Step n-1 (by taking a single 1-step).
• Step n-2 (by taking a single 2-step).

There are no other ways to arrive at exactly step n.

Step 2: State and Recurrence Relation

• State: Let dp[i] be the number of distinct ways to reach step i.
• Recurrence: The total ways to reach step i is the sum of the ways to reach the steps from which you can jump to i. Therefore:
  $dp[i]=dp[i-1]+dp[i-2]$

This is the Fibonacci recurrence relation. The logic is that every path to i-1 can be extended to i with a 1-step, and every path to i-2 can be extended to i with a 2-step.

The following video provides an excellent walkthrough, from the initial brute-force recursive thinking to the final optimized DP solution.

Steps 3-5: Implementation and Optimization

As shown in the video and our previous lesson, we can now implement the solution.

1. Tabulation (O(n) space):

   • State: dp array of size n+1.
   • Base Cases: dp[0] = 1 (one way to be at the start), dp[1] = 1 (one way to climb one step).
   • Loop: for i from 2 to n, apply dp[i] = dp[i-1] + dp[i-2].
   • Result: dp[n].

2. Space-Optimized (O(1) space):

   • Since we only need the last two values, we can use two variables. Let's call them one_step_back and two_steps_back.
   • Initialize one_step_back = 1, two_steps_back = 1.
   • Loop n-1 times, and in each iteration, calculate current = one_step_back + two_steps_back, then update two_steps_back = one_step_back and one_step_back = current.

The following reading provides a concise summary of the intuition, solution approach, and a clean Python implementation.

Problem 2: House Robber (LeetCode 198)

Now let's apply the same pattern to a slightly different problem. This problem is another interview favorite.

The Problem: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money. The only constraint is that you cannot rob adjacent houses. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob.

Step 1: Understanding the Choices

When you are at house i, you have two choices:

1. Rob house i: If you do, you cannot rob house i-1. The maximum money you could have up to this point would be nums[i] plus the maximum you could have robbed up to house i-2.
2. Do NOT rob house i: If you skip house i, the maximum money you can have is simply the maximum you could have robbed up to house i-1.

Step 2: State and Recurrence Relation

• State: Let dp[i] be the maximum amount of money you can rob from the first i houses (i.e., from index 0 to i-1 of the nums array).
• Recurrence: Based on the choices above, the maximum money you can get at house i is the max of the two scenarios:
  $dp[i]=\max (dp[i-1],dp[i-2]+\text{nums}[i-1])$
  • dp[i-1] corresponds to not robbing house i (index i-1).
  • dp[i-2] + nums[i-1] corresponds to robbing house i.

This video from NeetCode explains the problem with the same clear, step-by-step reasoning.

Steps 3-5: Implementation and Optimization

1. Tabulation (O(n) space):

   • State: dp array of size n+1.
   • Base Cases: dp[0] = 0 (no houses, no money), dp[1] = nums[0] (one house, rob it).
   • Loop: for i from 2 to n, apply dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]).
   • Result: dp[n].

2. Space-Optimized (O(1) space):

   • Similar to Climbing Stairs, dp[i] only depends on dp[i-1] and dp[i-2]. We can use two variables. Let's call them rob1 (max money up to i-2) and rob2 (max money up to i-1).
   • Initialize rob1 = 0, rob2 = 0.
   • Loop through each number n in nums:
     • Calculate new_rob = max(rob2, rob1 + n). This is our recurrence.
     • Update rob1 = rob2.
     • Update rob2 = new_rob.
   • The final answer is rob2.

For another perspective, this article breaks down the problem using a structured framework.

def minCostClimbingStairs(cost):
    # cost1 = min cost to reach step i-2
    # cost2 = min cost to reach step i-1
    cost1, cost2 = 0, 0
    
    for c in cost:
        # dp[i] = c + min(dp[i-1], dp[i-2])
        # Note: the cost 'c' is the cost of the *current* step, which is different from the problem statement's indexing.
        # A clearer way:
        # Let cost1 be the min cost to reach the previous step
        # Let cost2 be the min cost to reach two steps ago
        
        # current_cost is the cost to reach the *next* step from either i-1 or i-2
        current_cost = c + min(cost1, cost2)
        cost2 = cost1
        cost1 = current_cost
        
    # The final answer is the min cost to reach one step past the end
    # which is min(cost1, cost2)
    return min(cost1, cost2)

# A more direct implementation using the problem's indexing
def minCostClimbingStairs_v2(cost):
    n = len(cost)
    dp = [0] * (n + 1) # dp[i] is min cost to reach step i
    
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        
    return dp[n]

Conclusion

Today, we solidified the 1D Dynamic Programming pattern by applying it to two essential interview problems. You have practiced the complete workflow: from understanding the problem's choices to deriving a recurrence, and from implementing a simple tabulated solution to optimizing it for space.

Key Takeaways:

• 1D DP Pattern: Most 1D DP problems can be solved by defining a state dp[i] that represents the solution for the prefix of size i, and then finding a recurrence that relates dp[i] to dp[i-1] and dp[i-2].
• Climbing Stairs: This is a variation of the Fibonacci sequence. The number of ways to reach a state is the sum of ways to reach previous states. dp[i] = dp[i-1] + dp[i-2].
• House Robber: This is a "choice" problem. The optimal solution at a state is the max or min of choices made at that state. dp[i] = max(dp[i-1], dp[i-2] + value[i]).
• Space Optimization: Always be on the lookout to optimize space. If your recurrence only depends on a constant number of previous states, you can almost certainly get to an O(1) space solution.

In our next lesson, we will extend these ideas to a new dimension. We'll tackle 2D Dynamic Programming, where the state dp[i][j] depends on two variables. This is common in problems involving grids, matrices, or two strings, like the famous "Longest Common Subsequence" problem. The core skills of defining state and finding a recurrence will remain just as critical.