原题链接

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

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

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

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

动态规划三要素

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

重叠子问题

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

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

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

最优子结构

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

状态转移方程

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

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

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

constclimbStairs=function(n){constdp=[]dp[0]=1dp[1]=1for(leti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]}returndp[n]}

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

优化

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

constclimbStairs=function(n){leta1=1leta2=1for(leti=2;i<=n;i++){[a1,a2]=[a2,a1+a2]}returna2}

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