原题链接

虽然动态规划的最终版本 (降维再去维) 大都不是递归，但解题的过程还是离不开递归的。

如果你觉得你对递归理解的还不够透彻，请移步我的这篇专栏你真的懂递归吗？

新手可能会觉得动态规划思想接受起来比较难，确实，动态规划求解问题的过程不太符合人类常规的思维方式，我们需要切换成机器思维。

使用动态规划思想解题，首先要明确动态规划的三要素。

动态规划三要素

• 重叠子问题
• 最优子结构
• 状态转移方程

重叠子问题

切换机器思维，自底向上思考。

爬第 n 阶楼梯的方法数量，等于两部分之和：

• 爬上 n-1 阶楼梯的方法数量
• 爬上 n-2 阶楼梯的方法数量

最优子结构

子问题的最优解能够推出原问题的优解。

状态转移方程

dp[n] = dp[n-1] + dp[n-2]

具备三要素，确认边界条件，初始化状态，开始切菜：

• dp[0] = 1
• dp[1] = 1

const climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化

在此基础上，我们还可以通过压缩空间来对算法进行优化。因为 dp[i] 只与 dp[i-1] 和 dp[i-2] 有关，没有必要存储所有出现过的 dp 项，只用两个临时变量去存储这两个状态即可。

const climbStairs = function(n) {
    let a1 = 1
    let a2 = 1
    for (let i = 2; i <= n; i++) {
        [a1, a2] = [a2, a1 + a2]
    }
    return a2
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)