Solving 1D Dynamic Programming Problems

Greetings. In our previous lessons, we built a solid foundation in dynamic programming by exploring the Fibonacci sequence. You learned how to optimize a naive recursive solution using both top-down memoization and bottom-up tabulation, and even refined the tabulation approach to use constant space.

Today, we will apply this toolkit to a classic competitive programming problem: "Climbing Stairs." This lesson serves as a bridge from the mathematical purity of Fibonacci to the world of narrative-driven problems you'll frequently encounter. Our objective is to take a seemingly new problem, deconstruct it to find its underlying recursive structure, and solve it efficiently using the DP patterns you now know.

1. Understanding the Problem: Climbing Stairs

First, let's clearly define the problem.

Climbing Stairs Problem

This article from EnjoyAlgorithms introduces the problem with clear examples.

Read the section Let’s understand the problem to get a firm grasp of the goal and constraints. Pay attention to the examples for n=3 and n=5.

The task is to count the number of distinct ways to reach the n-th stair if you can only take steps of size 1 or 2. The order of steps matters, so [1, 2] is a different path from [2, 1].

2. Finding the Recurrence Relation

Dynamic programming problems are built on the principles of optimal substructure and overlapping subproblems. To uncover this structure, we first need to define a recurrence relation. How can we break the problem of reaching stair n into smaller, similar problems?

Think about the final step you take to land on stair n. There are only two possibilities:

You were on stair n-1 and took a single step.
You were on stair n-2 and took a two-step jump.

There are no other ways to arrive at exactly stair n. This insight is the key.

This diagram shows that to reach 'Step i', you must have come from either 'Step i-1' or 'Step i-2'.

This means the total number of ways to reach stair n is simply the sum of the ways to reach stair n-1 and the ways to reach stair n-2. If we define a function ways(i) as the number of ways to reach stair i, we get the recurrence relation:

ways (n) = ways (n - 1) + ways (n - 2)

The following video from the "take U forward" channel presents a structured way to think about finding such recurrence relations, which you may find helpful for future problems.

DP 2. Climbing Stairs | Learn How to Write 1D Recurrence Relations

This video introduces a general three-step "trick" for formulating recurrence relations in 1D DP problems.

Watch from the first step. The presenter explains how to think about DP problems (counting ways, min/max), and then applies a three-step process: represent the problem by an index, explore all actions on that index, and combine the results (summing, in this case). This formalizes the intuition we just used.

Does this recurrence look familiar? It's exactly the same as the one for Fibonacci numbers! The only difference lies in the base cases.

Ways to reach stair 1: ways(1) = 1 (Just take one step).
Ways to reach stair 2: ways(2) = 2 (Take two 1-step jumps, or one 2-step jump).

This is a crucial realization: "Climbing Stairs" is just the Fibonacci sequence in disguise. We can therefore solve it using the exact same optimization techniques.

3. From Naive Recursion to Optimized DP

Let's walk through the progression from a simple but inefficient solution to a highly optimized one.

The Brute-Force Recursive Approach

A direct translation of the recurrence ways(n) = ways(n-1) + ways(n-2) gives us a simple recursive function.

Climbing Stairs Problem

This section details the brute-force recursive solution and analyzes its complexity.

Read the section Brute force approach. The article clearly derives the recurrence and shows that its time complexity, T(n) = T(n-1) + T(n-2), is exponential, O(2^n).

Just like with Fibonacci, this approach is extremely slow because it re-computes the same subproblems over and over. For example, to calculate ways(5), we would calculate ways(3) and ways(4). The call for ways(4) would then again trigger a calculation for ways(3).

This recursion tree for `countWays(4)` illustrates the problem of overlapping subproblems. Notice that `countWays(2)` is computed twice, leading to redundant work.

To fix this, we introduce dynamic programming.

Applying Memoization (Top-Down DP)

Our first optimization is memoization. We use the same recursive structure but store the result for each stair i in a cache (or "memo") the first time we compute it. Subsequent calls for ways(i) will just return the cached value in $O (1)$ time.

70. Climbing Stairs - Solution & Explanation

The NeetCode article provides a clear implementation of the memoized solution.

Read Section 2, Dynamic Programming (Top-Down). Examine the algorithm steps and the C++ code. See how it's almost identical to the naive recursion, but with the addition of a cache check.

This simple addition transforms the complexity from exponential to linear, $O (n)$ , at the cost of $O (n)$ space for the cache and the recursion stack.

Applying Tabulation (Bottom-Up DP)

For competitive programming, the iterative bottom-up approach is often preferred as it avoids recursion overhead and the risk of stack overflow. We build a dp array from the bottom up.

The logic is as follows:

Declare a DP array: Create an array dp of size n+1. dp[i] will store the number of ways to reach stair i.
Initialize base cases: We know dp[1] = 1 and dp[2] = 2.
Iterate and fill: Loop from i = 3 to n, applying our recurrence: dp[i] = dp[i-1] + dp[i-2].
Final answer: The result is dp[n].

70. Climbing Stairs - Solution & Explanation

This section explains the bottom-up approach with clear code.

Now, read Section 3, Dynamic Programming (Bottom-Up). Again, focus on the algorithm and the C++ implementation. Notice how it directly mirrors the logic we just outlined.

This approach also has a time complexity of $O (n)$ and a space complexity of $O (n)$ .

Space Optimization

Can we do better? Look at the tabulation recurrence: dp[i] = dp[i-1] + dp[i-2]. To calculate the number of ways for the current stair, we only need the results for the previous two stairs. We don't need dp[i-3] or any earlier values. This means we can discard the full dp array and use just two variables to keep track of the last two results.

Climbing Stairs | LeetCode 70 | C++, Python

This video from Knowledge Center clearly explains the logic of space optimization and provides a code walkthrough.

Watch the segment from the base case. The presenter illustrates how to use two variables to iteratively compute the result, effectively sliding a window of size two up the staircase. This reduces the space complexity to O(1) while keeping the time complexity at O(n). The C++ implementation follows.

This space-optimized tabulation is the most efficient solution for this problem. It's a powerful technique to always keep in mind when your DP recurrence only depends on a fixed number of previous states.

Conclusion

In this lesson, you successfully applied your foundational DP knowledge to a classic problem. You saw how a problem with a narrative can be broken down into a mathematical recurrence, revealing a familiar structure.

Key Takeaways:

Problem Modeling: The first step in solving DP problems is to find the recurrence relation by analyzing how to break the problem into smaller subproblems. For "Climbing Stairs," this was ways(n) = ways(n-1) + ways(n-2).
Pattern Recognition: The "Climbing Stairs" problem is structurally identical to the Fibonacci sequence, allowing us to reuse the same optimization strategies.
DP Application: We solved the problem using memoization (top-down), tabulation (bottom-up), and finally a space-optimized tabulation approach.
Efficiency: The most efficient solution runs in $O (n)$ time and $O (1)$ space, a massive improvement over the naive $O (2^{n})$ recursive solution.

You've now moved from a purely mathematical exercise to solving a complete competitive programming problem with DP. In the next lesson, we will increase the complexity slightly by moving from a 1D problem to a 2D problem on a grid, further expanding your DP problem-solving arsenal.

Recommended resources