70. Climbing Stairs

Leetcode link

题目简介

/**
 * @param {number} n
 * @return {number}
 */

题目给我们一个数字 n 代表需要登上的台阶数量

登上台阶的方法有：

1. 一次上一阶
2. 一次上两阶

题目要求我们计算，一共有多少种方法可以登上第 n 阶

解题思路

通过观察我们发现，这个问题满足动态规划的条件：

首先，这个问题可以被拆分成多个子问题（满足 最优子结构性质）：

• 假设登上台阶 n 的状态为 f(n)
• f(n) 可以拆分成 f(n-1) 与 f(n-2)

其次，多个子问题是有重复性质的（满足 子问题重叠性质）：

• f(n-1) 可以被拆分成 f(n-2) 与 f(n-3)
• f(n-2) 重复了

最后，最终的问题并不会影响到子问题的结果（满足 无后效性）：

• f(n) 的结果并不会影响到 f(n-1)

接下来我们只需要确定初始状态以及状态转移方程就可以用 dp 求解了

状态转移方程：

• f(n) = f(n-1) + f(n-2)
• 解释：登上第 n-1 个台阶的可能方法数 + 登上第 n-2 个台阶可能的方法数 = 登上第 n 个台阶的可能方法数

初始状态：

• f(1)=1；f(2)=2
• 解释：登上一个台阶，只能有一种方法、登上两个台阶可以：一次上一个，上两次；一次上两个（两种方法）

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    const dp = [1, 2]

    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    return dp[n - 1]
};