We did it! It’s day 31 of the Leetcode July Challenge and we’re wrapping up with a nice little question, Climbing Stairs. The problem’s premise is that you are climbing a flight of stairs with $n$ steps. While ascending, you can take the stairs one or two at a time from any given point. We’re asked to return the number of distinct ways to reach the top of the stairs. This seems like a case of counting permutations of 1 and 2 that sum to $n$, but I think we should be able to find a pattern to the permutations given the tightness of the constraints.

n = 1 step
   __	
__|

For 1 step, we only take the first step 1 at a time, so there’s only 1 way.

n = 2 steps
      __
   __|
__|

For 2 steps, we could take each step individually or take 2 steps directly to the top, so there are two ways to get to the top.

n = 3 steps
         __
      __|
   __|
__|

For 3 steps, we could take all single steps, a double step then a single step, or a single step then a double step, so three ways. The only pattern so far is $n+1$, but let’s check one more.

n = 4 steps
            __
         __|
      __|
   __|
__|

This is where things get interesting. For 4 steps we have: all single steps, all double steps, a double step then two single steps, single double single, and two single steps plus a double step. That’s five ways, but more importantly it’s the number of ways to get up 3 steps plus the number of ways to get up 2 steps.

We could do additional test cases for additional evidence or construct an inductive proof, but this looks like it fits a linear recurrence pattern, specifically a variation of the Fibonacci sequence, $[0,1,1,2,3,5,…,(f(n-1)+f(n-2))]$. We can construct a quick and dirty top-down, recursive algorithm to test against the first few cases.

// Simplest Top-Down Recursion
int climbStairs(int n) {
	if(n==1) return 1;
	if(n==2) return 2;
	return climbStairs(n-1) + climbStairs(n-2);
}

That works! Knowing we’re working in this linear recurrence space we can develop a more efficient algorithm based on dynamic programming with a memoization table that stores the number of step permutations for all previous stair lengths.

// Bottom-Up DP with Memoization Table
int climbStairs(int n) {
	int dp[n+1];
	dp[0]=1;
	dp[1]=1;
	for(int i=2;i<=n;i++){
		dp[i]=dp[i-1]+dp[i-2];
	}
	return dp[n];
}

A common optimization of this approach comes from noticing that we only ever use $n-1$ and $n-2$ values from the memoization table. We could just as easily store only these variables and step them up at each iteration to save some memory–from linear to constant space complexity, with a linear runtime complexity.

// Bottom-Up DP with Memoization Variables
int climbStairs(int n) {
	int n0 = 1;
	int n1 = 1;
	int n2 = n1;
	for(int i=2;i<=n;i++) {
		n2 = n0 + n1;
		n0 = n1;
		n1 = n2;
	}
	return n2;
}

As a bonus, there is a closed form equation for calculating the $n^{th}$ Fibonacci number using the Golden Ratio. We can easily apply that formula to our problem. It’s not very interesting algorithmically, but neat nonetheless.

// Closed Form Equation using Golden Ratio- Binet's formula
int climbStairs(int n) {
	return round(pow(((1+sqrt(5))/2),n+1)/sqrt(5));
}

Well, I’ve enjoyed journaling my progress through this month’s problems so much, that I’ll continue to make similar posts when I come across interesting problems that I think would benefit from discussion. Thanks for checking out my posts!