Climbing Stairs Using Dynamic Programming

56.4k
0

A staircase contains n steps, with ground level treated as step 0. Every move can climb either 1 step or 2 steps.

Return the number of distinct jump sequences ending exactly at step n. Different jump orders count as different sequences.

Example 1

Input: n = 4
Output: 5
Explanation: Five valid sequences reach step 4: [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], and [2, 2].

Example 2

Input: n = 1
Output: 1
Explanation: A single 1-step jump forms the only valid sequence.

Recursion

Every valid climb ends with either a 1-step jump or a 2-step jump. Routes ending with different final jump sizes never overlap, so both route groups can be counted separately and added.

The smaller counting task repeats for lower step numbers, making recursion a natural fit. Let solve(step) represent the number of sequences ending at step. The public method starts with solve(n) because target state n represents the complete staircase. Ground level completes one sequence, while a negative step completes none.

Algorithm

  • Define solve(step) as the count for a target step so every recursive call keeps one clear state meaning.

  • Return 1 for step = 0 because an exact landing at ground level completes one valid sequence.

  • Return 0 for step < 0 because a jump below ground cannot belong to a valid sequence.

  • Explore solve(step - 1) so every sequence ending with a 1-step jump contributes to the count.

  • Explore solve(step - 2) so every sequence ending with a 2-step jump contributes to the count.

  • Add both branch answers because the two final-jump groups are disjoint, then return the combined count.

Dry Run

Climbing Stair Rec

Climbing Stair Rec

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts paths ending at a requested step.
int solve(int step) {
// Ground level completes one valid sequence.
if (step == 0) {
return 1;
}
// A negative step cannot complete a valid sequence.
if (step < 0) {
return 0;
}
// A 1-step final jump starts one step below.
int oneStepJump = solve(step - 1);
// A 2-step final jump starts two steps below.
int twoStepJump = solve(step - 2);
// Disjoint final-jump groups combine by addition.
return oneStepJump + twoStepJump;
}
public:
// Returns the number of valid climbing sequences.
int climbStairs(int n) {
// Target state n represents the full staircase.
return solve(n);
}
};
// Driver code
int main() {
int n = 4;
Solution obj;
cout << obj.climbStairs(n);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2n), a recursive state can create two smaller calls across a depth of at most n.

Space Complexity: O(n), the deepest active branch contains at most n recursion stack frames.

Memoization

Direct recursion revisits the same target steps many times. For example, solve(2) appears inside branches for both solve(3) and solve(4). The duplicate work grows quickly even though every repeated state has an identical answer.

Memoization keeps the recursive choices and adds a dp array. A calculated count is saved under the matching step number, and later calls reuse the saved count. The state, base cases, and initial solve(n) call remain unchanged, so only repeated work disappears.

Algorithm

  • Create a dp array of size n + 1 filled with -1 so every uncalculated state has a clear marker.

  • Keep solve(step, dp) as the recursive state so memoization preserves the original counting meaning.

  • Handle step = 0 and step < 0 first because stopping states need no cache access.

  • Return dp[step] after a cache hit so an already solved staircase height avoids another recursion tree.

  • Compute both 1-step and 2-step final-jump branches because every valid sequence belongs to exactly one branch.

  • Store the branch sum in dp[step] so later requests can reuse the complete count, then return the saved value.

Dry Run

Climbing Stair Memo

Climbing Stair Memo

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts paths and stores calculated results.
int solve(int step, vector<int>& dp) {
// Ground level completes one valid sequence.
if (step == 0) {
return 1;
}
// A negative step cannot complete a valid sequence.
if (step < 0) {
return 0;
}
// A saved count avoids repeated recursive work.
if (dp[step] != -1) {
return dp[step];
}
// A 1-step final jump starts one step below.
int oneStepJump = solve(step - 1, dp);
// A 2-step final jump starts two steps below.
int twoStepJump = solve(step - 2, dp);
// The full count joins both final-jump groups.
dp[step] = oneStepJump + twoStepJump;
// The saved count finishes the current state.
return dp[step];
}
public:
// Returns the count using memoized recursion.
int climbStairs(int n) {
// Minus one marks every uncalculated state.
vector<int> dp(n + 1, -1);
// Target state n represents the full staircase.
return solve(n, dp);
}
};
// Driver code
int main() {
int n = 4;
Solution obj;
cout << obj.climbStairs(n);
return 0;
}

Complexity Analysis

Time Complexity: O(n), each reachable step from 0 through n is calculated at most once.

Space Complexity: O(n), the dp array stores n + 1 counts and the recursion stack reaches a depth of at most n.

Tabulation

Memoization begins at the target and discovers smaller states through recursive calls. Tabulation reverses the direction. Known counts for the smallest steps are stored first, and each larger count is built from two already available entries.

The state meaning stays unchanged: dp[step] stores the number of sequences ending at step. Increasing step order guarantees both needed earlier counts before every update, so recursion and recursion-stack storage disappear.

Algorithm

  • Create a dp array of size n + 1 so every staircase height has a dedicated count.

  • Store dp[0] = 1 because ground level represents one completed empty sequence.

  • Store dp[1] = 1 for a positive staircase because a single 1-step jump is the only route.

  • Process steps from 2 through n in increasing order so both earlier counts are ready before each update.

  • Set dp[step] = dp[step - 1] + dp[step - 2] because every route ends with exactly one allowed jump size.

  • Return dp[n] because target state n represents the complete staircase.

Dry Run

Climbing Stair Tabulation

Climbing Stair Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the count using bottom-up tabulation.
int climbStairs(int n) {
// One table entry stores each step count.
vector<int> dp(n + 1, 0);
// Ground level represents one empty sequence.
dp[0] = 1;
// A positive staircase needs the first base count.
if (n >= 1) {
dp[1] = 1;
}
// Increasing order keeps both earlier counts ready.
for (int step = 2; step <= n; step++) {
// Both final-jump groups form the current count.
dp[step] = dp[step - 1] + dp[step - 2];
}
// Target entry stores the complete answer.
return dp[n];
}
};
// Driver code
int main() {
int n = 4;
Solution obj;
cout << obj.climbStairs(n);
return 0;
}

Complexity Analysis

Time Complexity: O(n), one constant-time transition is evaluated for every step from 2 through n.

Space Complexity: O(n), the dp array stores one count per step while iterative order removes recursion-stack usage.

Space Optimization

Tabulation stores every step count, but a new count only needs the previous two entries. Counts farther behind can no longer influence a later transition after both required neighbors move forward.

Two variables can therefore replace the dp array. prev2 represents dp[step - 2], and prev1 represents dp[step - 1]. The sum becomes current, then the variables shift in left-to-right state order so the next step receives the correct pair.

Algorithm

  • Return 1 for n <= 1 because ground level and the first step each have one valid sequence.

  • Set prev2 = 1 for step 0 so the two-step-back count starts with the empty sequence.

  • Set prev1 = 1 for step 1 so the one-step-back count starts with the only direct jump.

  • Process steps from 2 through n in increasing order so both retained counts match the current transition.

  • Compute current = prev1 + prev2 because the final 1-step and 2-step jump groups form the full count.

  • Shift prev2 to old prev1 and prev1 to current so the next iteration keeps the newest two counts.

  • Return prev1 because the final shift places the count for step n in the one-step-back variable.

Dry Run

Climbing Stair

Climbing Stair

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the count using constant extra space.
int climbStairs(int n) {
// The two smallest targets each have one sequence.
if (n <= 1) {
return 1;
}
// Previous values represent steps zero and one.
int prev2 = 1;
int prev1 = 1;
// Increasing order keeps the retained states aligned.
for (int step = 2; step <= n; step++) {
// Both final-jump groups form the current count.
int current = prev1 + prev2;
// Left shift preserves the newest two counts.
prev2 = prev1;
prev1 = current;
}
// Final prev1 represents target step n.
return prev1;
}
};
// Driver code
int main() {
int n = 4;
Solution obj;
cout << obj.climbStairs(n);
return 0;
}

Complexity Analysis

Time Complexity: O(n), one constant-time update is performed for every step from 2 through n.

Space Complexity: O(1), only prev2, prev1, current, and loop variables are retained regardless of n.

Interview follow-up Questions

Every route to a target step arrives from one step below or two steps below. Adding both non-overlapping route groups creates the Fibonacci-style growth pattern.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or secon...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0