Description

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.

1// Initialize our base cases, one and two. Return two at the end
2 
3var climbStairs = function (n) {
4  if (n == 1) return 1
5  var one = 1
6  var two = 2
7 
8  return two
9};

1// We guard for n being 1 as well
2 
3function climbStairs(n: number): number {
4  if (n == 1) return 1
5  var one = 1
6  var two = 2
7 
8  return two
9};

1//
2 
3class Solution {
4  int climbStairs(int n) {
5    if (n == 1) {
6      return 1;
7    }
8 
9    int one = 1;
10    int two = 2;
11 
12    return two;
13  }
14}

1// Explicit typing of Java with int
2 
3class Solution {
4  public int climbStairs(int n) {
5    if (n == 1) {
6      return 1;
7    }
8    int one = 1;
9    int two = 2;
10 
11    return two;
12  }
13}

1#
2 
3class Solution:
4  def climbStairs(self, n: int) -> int:
5    if n == 1:
6      return 1
7    one = 1
8    two = 2
9 
10    return two

1// Type inference with :=
2 
3func climbStairs(n int) int {
4  if n == 1 {
5    return n
6  }
7 
8  one := 1
9  two := 2
10 
11  return two
12}

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.

1//
2 
3var climbStairs = function (n) {
4  if (n == 1) return 1
5  var one = 1
6  var two = 2
7 
8  for (var i = 3; i < n + 1; i++) {
9    var tmp = one + two
10    one = two
11    two = tmp
12  }
13  return two
14};

1//
2 
3function climbStairs(n: number): number {
4  if (n == 1) return 1
5  var one = 1
6  var two = 2
7 
8  for (var i = 3; i < n + 1; i++) {
9    var tmp = one + two
10    one = two
11    two = tmp
12  }
13  return two
14};

1//
2 
3class Solution {
4  int climbStairs(int n) {
5    if (n == 1) {
6      return 1;
7    }
8    int one = 1;
9    int two = 2;
10 
11    for(var i = 3; i < n + 1; i++) {
12      var tmp = one + two;
13      one = two;
14      two = tmp;
15    }
16    return two;
17  }
18}

1//
2 
3class Solution {
4  public int climbStairs(int n) {
5    if (n == 1) {
6      return 1;
7    }
8    int one = 1;
9    int two = 2;
10 
11    for (var i = 3; i < n + 1; i++) {
12      int tmp = one + two;
13      one = two;
14      two = tmp;
15    }
16    return two;
17  }
18}

1#
2 
3class Solution:
4  def climbStairs(self, n: int) -> int:
5    if n == 1:
6      return 1
7    one = 1
8    two = 2
9 
10    for i in range(3, n + 1):
11      tmp = two
12      two = one + two
13      one = tmp
14    return two

1//
2 
3func climbStairs(n int) int {
4  if n == 1 {
5    return n
6  }
7 
8  one := 1
9  two := 2
10 
11  for i := 3; i < n + 1; i++ {
12    tmp := one + two
13    one = two
14    two = tmp
15  }
16  return two
17}

Questions? Concerns?

Please comment a better solution if you have one.