70.Climbing Stairs

tags: Easy,Math,Memoization,DP

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?

範例

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

• 1 <= n <= 45

解答

C++

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 0;
        while (n--) {
            b = (a += b) - b;
        }
        return a;
    }
};

Yen-Chi ChenMon, Dec 12

Javascript

function climbStairs(n) {
  const fib = [1, 1, 2, 3];
  for (let i = 4; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  return fib[n];
}

Time:

$O(n)$
Space:

$O(n)$

function climbStairs(n) {
  if (n < 4) return n;
  let a = 1;
  let b = 2;
  let result = 0;
  for (let i = 3; i <= n; i++) {
    result = a + b;
    a = b;
    b = result;
  }

  return result;
}

Time:

$O(n)$
Space:

$O(1)$

Marsgoat Dec 12, 2022

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        fn, fnn, fnnn = 1, 2, 0
        for _ in range(3, n+1):
            fnnn = fn + fnn
            fn, fnn = fnn, fnnn

        return fnnn if n > 2 else (fnn if n == 2 else fn)

KobeMon, Dec 12

C#

public class Solution {
    public int ClimbStairs(int n) {
        if (n <= 2) return n;

        int a = 1;
        int b = 2;
        
        for (int i = 3; i <= n; i++) {
            int temp = b; 
            b = a + b;
            a = temp;
        }
        
        return b;
    }
}

JimMon, Dec 12

Reference

回到題目列表