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]
}