70. Climbing Stairs

70. Climbing Stairs

思路

DP。走到第n级的走法f(n)有f(n) = f(n-1) + f(n-2)。

source code

1
2
3
4
5
6
7
8
9
10
// Runtime: 56 ms, faster than 46.66% of JavaScript online submissions for Climbing Stairs.
// Memory Usage: 32.8 MB, less than 100.00% of JavaScript online submissions for Climbing Stairs.
var climbStairs = function (n) {
  const arr = [1, 1];
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  return arr[n];
};

test cases

1
2
3
4
5
6
7
8
9
10
11
test("test1", () => {
  expect(climbStairs(2)).toEqual(2);
});

test("test2", () => {
  expect(climbStairs(0)).toEqual(1);
});

test("test3", () => {
  expect(climbStairs(3)).toEqual(3);
});