ClimbingStairs.java

/*
  Climbing Stairs - LeetCode: https://leetcode.com/problems/climbing-stairs

  An adaption of the Leetcode "Solution" section with many comments added
  for teaching purposes: https://leetcode.com/problems/climbing-stairs/solution/

  The video to explain this code is here: https://www.youtube.com/watch?v=NFJ3m9a1oJQ
*/

/*
  Time Limit Exceeded

  If we don't cache answers we will repeat subproblems we
  already have the answer to
*/
class TopDownWithoutMemoization {

  public int climbStairs(int n) {
    return climbStairsHelper(n);
  }

  public int climbStairsHelper(int n) {

    /*
      0 distinct ways to climb negative steps if we
      can only take 1 or 2 steps
    */
    if (n < 0) {
      return 0;
    }

    /*
      1 distinct way to climb 1 if we can only take 1
      or 2 steps.

      We take 1 step.
    */
    if (n == 0) {
      return 1;
    }

    /*
      The answer to this subproblem is the sum of the answer to the
      subproblems n - 1 and n - 2

      This drills us towards our base cases that bring us back up with
      an answer
    */
    return climbStairsHelper(n - 1) + climbStairsHelper(n - 2);
  }

}

/*
  This code passes all Leetcode test cases as of Jan. 13 2019
  Runtime: 3 ms, faster than 98.87% of Java online submissions for Climbing Stairs.

  We now cache our previous answers. Therefore, we have a linear time compleity thus
  letting this code pass
*/
class TopDownWithMemoization {

  public int climbStairs(int n) {
    int memo[] = new int[n + 1];
    return climbStairsHelper(n, memo);
  }

  public int climbStairsHelper(int n, int memo[]) {

    /*
      0 distinct ways to climb negative steps if we
      can only take 1 or 2 steps
    */
    if (n < 0) {
      return 0;
    }

    /*
      1 distinct way to climb 1 if we can only take 1
      or 2 steps.

      We take 1 step.
    */
    if (n == 0) {
      return 1;
    }

    /*
      Do we already have an answer to this question (subproblem)?
      If not fall through and compute, BUT if we already know it
      just return it from the cache
    */
    if (memo[n] > 0) {
        return memo[n];
    }

    /*
      The answer to this subproblem is the sum of the answer to the
      subproblems n - 1 and n - 2

      This drills us towards our base cases that bring us back up with
      an answer

      We cache the answer before returning it so we have it later
    */
    memo[n] = climbStairsHelper(n - 1, memo) + climbStairsHelper(n - 2, memo);

    return memo[n];
  }

}

/*
  This code passes all Leetcode test cases as of Jan. 13 2019
  Runtime: 3 ms, faster than 98.87% of Java online submissions for Climbing Stairs.

  The bottom up approach. We start from the "bottom" and build up to n
*/
class BottomUp {

  public int climbStairs(int n) {

    /*
      In programming we all know we index off of 0. This is why
      we create an array of size n + 1. It is so we can just return
      dp[n] at the end instead of fumbling with dp[n - 1].

      If n = 4 we will get an array like this if we just did "new int[n];":
      [0, 0, 0, 0]
       0  1  2  3

      If we instead do "new int[n + 1" we have:
      [0, 0, 0, 0, 0]
       0  1  2  3  4

       And now we can be literal in how we access the nth subproblem
    */
    int[] dp = new int[n + 1];

    /*
      n = 0, the answer is 1. We can only take no steps.
    */
    dp[0] = 1;

    /*
      n = 1, the answer is 1. We can only take 1 step.
    */
    dp[1] = 1;

    /*
      The answer to the ith subproblem is the sum between the answer
      to the subproblems of climbing i - 1 stairs and i - 2 stairs
    */
    for (int i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
    }

    /*
      This is what we want and built to the while way. The answer for
      the total unique ways to climb n steps when we can either take a
      1 step or 2 step
    */
    return dp[n];
  }

}