Climbing Stairs Editorial

Practice Problem Link: Climbing Stairs

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

There is a staircase with n steps. You need to reach the top and you can either climb 1 step or 2 steps at a time. In how many distinct ways can you reach the top of the staircase.

Naive Approach

We can solve it naively with a recursive brute force approach. The number of ways to reach the ith stair is the sum of the number of ways to reach the stair i - 1 and stair i - 2.

Analysis

• Time Complexity: O(2ⁿ)
• Space Complexity: O(n)

Implementation

C++

int recursiveStairs(int n) {
	if(n == 1) {
		return 1;
	}
	else if(n == 2) {
		return 2;
	}
	return recursiveStairs(n - 1) + recursiveStairs(n - 2);
}
int climbStairs(int n) {
    return recursiveStairs(n);
}

Java

class Solution {
	int recursiveStairs(int n) {
		if(n == 1) {
			return 1;
		}
		else if(n == 2) {
			return 2;
		}
		return recursiveStairs(n - 1) + recursiveStairs(n - 2);
	}
	int climbStairs(int n) {
	    return recursiveStairs(n);
	}
}

Optimal Approach

We can observe in this problem, that multiple function calls get called over and over again redundantly here, i.e there is some overlapping subproblem here. This hints at the use of DP to memoize the brute recursion and improved the solution to linear time.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

int dp[50];
int recursiveStairs(int n) {
	if(n == 1) {
		return 1;
	}
	else if(n == 2) {
		return 2;
	}
	else if(dp[n] != - 1) {
		return dp[n];
	}
	return dp[n] = recursiveStairs(n - 1) + recursiveStairs(n - 2);
}
int climbStairs(int n) {
	memset(dp, -1, sizeof(dp));
    return recursiveStairs(n);
}

Java

class Solution {
	int dp[] = new int[50];
	int recursiveStairs(int n) {
		if(n == 1) {
			return 1;
		}
		else if(n == 2) {
			return 2;
		}
		else if(dp[n] != -1) {
			return dp[n];
		}
		return dp[n] = recursiveStairs(n - 1) + recursiveStairs(n - 2);
	}
	int climbStairs(int n) {
		for(int i = 0; i <= n; i++) {
			dp[i] = -1;
 		}
	    return recursiveStairs(n);
	}
}

Bottom Up Implementation

C++

vector<int> dp;
int climbStairs(int n) {
	if(n == 1) {
		return 1;
	} 
	dp.resize(n + 1);
	dp[1] = 1;
	dp[2] = 2;
	for(int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
    return dp[n];
}

Java

class Solution {
	int dp[];
	int climbStairs(int n) {
		if(n == 1) {
		return 1;
		} 
		dp = new int[n + 1];
		dp[1] = 1;
		dp[2] = 2;
		for(int i = 3; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}
}