# 动态规划

# 爬楼梯

# 题目是

假设husky正在爬楼梯，有n节台阶才能到达楼顶
每次husky都可以爬一个台阶或者两个台阶
问题是一共有多少种方法可以爬到楼顶

# show me the code

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

1
2
3
4
5
6
7
8
9
10

# 解析

爬楼梯动态规划解析图

由上图可见，我们可以递推出一个式子（需要台阶大于2）

最后一节的方法 = 前一个方法数 + 前前个的方法数

1

如果我们将这些数据都存储到数组中，那么接可以得出这样的式子

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

1

依次这样计算，然后再将数据存储起来，也就是循环遍历，直到最后不符合遍历条件，返回数组的最后一个数，就是爬到楼顶的方法数

← Array.sort()