70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution

Keep a running total of number of distinct jumps it took us to get to our previous two stairs.

On each loop, sum the values of the two previous stairs as the latest stair's value, our running total.

Setup base cases

Setup base cases of one and two whose values are 1 and 2.

We figure this out from the problem explanation.

Return two at the end of the function where we'll keep our summed total.

// Initialize our base cases, one and two. Return two at the end

var climbStairs = function (n) {
  if (n == 1) return 1
  var one = 1
  var two = 2

  return two
};

// We guard for n being 1 as well

function climbStairs(n: number): number {
  if (n == 1) return 1
  var one = 1
  var two = 2

  return two
};

//

class Solution {
  int climbStairs(int n) {
    if (n == 1) {
      return 1;
    }

    int one = 1;
    int two = 2;

    return two;
  }
}

// Explicit typing of Java with int

class Solution {
  public int climbStairs(int n) {
    if (n == 1) {
      return 1;
    }
    int one = 1;
    int two = 2;

    return two;
  }
}

#

class Solution:
  def climbStairs(self, n: int) -> int:
    if n == 1:
      return 1
    one = 1
    two = 2

    return two

// Type inference with :=

func climbStairs(n int) int {
  if n == 1 {
    return n
  }

  one := 1
  two := 2

  return two
}

Iterate until n + 1

We loop up til n + 1 because when we "land" on n + 1 then two will have the return value we want, the number of distinct ways to get to that stair.

//

var climbStairs = function (n) {
  if (n == 1) return 1
  var one = 1
  var two = 2

  for (var i = 3; i < n + 1; i++) {
    var tmp = one + two
    one = two
    two = tmp
  }
  return two
};

//

function climbStairs(n: number): number {
  if (n == 1) return 1
  var one = 1
  var two = 2

  for (var i = 3; i < n + 1; i++) {
    var tmp = one + two
    one = two
    two = tmp
  }
  return two
};

//

class Solution {
  int climbStairs(int n) {
    if (n == 1) {
      return 1;
    }
    int one = 1;
    int two = 2;

    for(var i = 3; i < n + 1; i++) {
      var tmp = one + two;
      one = two;
      two = tmp;
    }
    return two;
  }
}

//

class Solution {
  public int climbStairs(int n) {
    if (n == 1) {
      return 1;
    }
    int one = 1;
    int two = 2;

    for (var i = 3; i < n + 1; i++) {
      int tmp = one + two;
      one = two;
      two = tmp;
    }
    return two;
  }
}

#

class Solution:
  def climbStairs(self, n: int) -> int:
    if n == 1:
      return 1
    one = 1
    two = 2

    for i in range(3, n + 1):
      tmp = two
      two = one + two
      one = tmp
    return two

//

func climbStairs(n int) int {
  if n == 1 {
    return n
  }

  one := 1
  two := 2

  for i := 3; i < n + 1; i++ {
    tmp := one + two
    one = two
    two = tmp
  }
  return two
}

Questions? Concerns?

Please comment a better solution if you have one.