Using Top Down Dynamic Programming to Solve the Climbing Stairs Problem

Problem Statement

You are climbing a staircase. It takes n steps to reach the top. Each time you can either take 1 or 2 steps.

Understanding the Problem

The idea around this problem is pretty straightforward. We want to count unique permutations of steps that will help us reach the nth step.

High Level Algorithm

DP is an optimization on top of sub-problems (usually recursion), so before we use it, we still need to solve the problem.

  1. n == 0: return 1, we reached the nth step.
  1. Create an array to store each state you encounter and cache your calculation in the recursive case.
  2. Add another base case where you reuse the cache value if you have seen the state.

Runtime and Space Complexity

Runtime

The brute force recursive solution has a runtime of O(2^N). This is because for every N step, we can make 2 decisions:take 1 step or take 2 steps. This might be okay if N is small, but it exponentially grows larger as N increases.

Space Complexity

The space complexity of both of our solutions is O(N). In the brute force recursive solution, we are recursively going from 0 to N keeping them in our call stack. Everytime we finish a path, we would pop it out of our callstack so at most it’ll be O(N)

Implementation

Recursive solution

class Solution {
public int climbStairs(int n) {
return helper(n);
}

private int helper(int n) {
if (n == 0) {
// base case where we arrived at an answer
return 1;
} else if (n < 0) {
// base case where we went too far
return 0;
} else {
// recursive case where we try taking 1 step
// and 2 steps, adding the unique permuation
// of steps back
return helper(n-1) + helper(n-2);
}
}
}
class Solution {
private int[] memo;
public int climbStairs(int n) {
// instantiate the datastructure to cache the calculation
// to each of our subproblems. i.e. what step we are on
memo = new int[n+1];
return helper(n);
}

private int helper(int n) {
if (n < 0) {
return 0;
} else if (memo[n] != 0) {
// If we stored something in our cache reuse it and avoid
// recalculating everything
return memo[n];
} else if (n == 0) {
return 1;
} else {
// store our calculation inside our cache so we don't
// have to recalculate it again for memo[n]
memo[n] = helper(n-1) + helper(n-2);
return memo[n];
}
}
}

Conclusion

To solve Climbing Stairs we need to be able to solve the problem recursively and then apply DP via memoization (caching) to help optimize the runtime.

--

--

--

Software Engineer by day, side hustler wannabee by night! https://leetdev.io

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Project Management in 3 Minutes

Python for Data Science: From Scratch (Part I)

Demystifying Exceptions in Our Code

Testing of Apache Airflow’s DAGs with docker compose and pytest

Guide to a successful IT startup

Welcome to my Journey #1

Ceph RBD Performance Debug Journey

How To Send A HTML Form To Email Using PHP

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Josh Chang

Josh Chang

Software Engineer by day, side hustler wannabee by night! https://leetdev.io

More from Medium

Leetcode: 84. Largest Rectangle in Histogram

How Software Companies think: Understanding how they function

Steps to solve an algorithm

Dynamic Programming : What, Why and When?