Using Top Down Dynamic Programming to Solve the Climbing Stairs Problem

Problem Statement

Understanding the Problem

High Level Algorithm

  1. n < 0: return 0, we went too far
  2. n == 0: return 1, we reached the nth step.
  1. N > 0: try taking 1 step and 2 step
  1. Solve the problem using a Brute force recursive solution
  2. Create an array to store each state you encounter and cache your calculation in the recursive case.
  3. Add another base case where you reuse the cache value if you have seen the state.

Runtime and Space Complexity

Runtime

Space Complexity

Implementation

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

--

--

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