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

Analyze

• 到达当前的台阶的方法有两种:
  • 一种方法是从上一级台阶加一;
  • 另一种方法是从上上一级台阶加二;

所以到达当前台阶的方法之和可以用以下式子表示: f(n) = f(n - 1) + f(n - 2)。

因此该问题与解斐波那契数列是相同的场景。以下提供记忆化递归与动态规划两种解法:

• 记忆化递归方法:

const arr = [1, 2]

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n === 1) return arr[0]
  if (n === 2) return arr[1]

  if (arr[n]) return arr[n]
  arr[n] = climbStairs(n - 1) + climbStairs(n - 2)
  return arr[n]
}

• 动态规划方法:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  const arr = [1, 2]
  for (let i = 2; i < n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2]
  }

  return arr[n - 1]
}