70. 爬楼梯🔖DP

• https://leetcode.cn/problems/climbing-stairs/

动态规划

动态规划解题主要是解决两点：

1. 状态转移方程（定义子问题）
2. 初始状态

1. 状态转移方程

• 到达第n层阶梯的方式只有两种，走一步然后结束，或者走两步然后结束。
• 到达第n-1层阶梯的方式只有两种，走一步然后结束，或者走两步然后结束。
• ……

可以用数学函数表达如下式：

f(n) = f(n-1) + f(n - 2)

2. 初始状态

• 从问题角度考虑：如果阶梯只有一层或者只有两层，显然上述公式不符合带入
• 从数学函数角度考虑：函数f的定义域一定是大于0的

所以函数模型可以抽象出来：

f(1) = 1,(当n = 1)
f(2) = 2,(当n = 2)
f(n) = f(n-1) + f(n - 2)

function climbStairs(n: number): number {
  if (n <= 2) return n
  const arr = new Array(n).fill(0)
  arr[0] = 1
  arr[1] = 2
  for (let i = 2; i < arr.length; i++) 
    arr[i] = arr[i-1] + arr[i-2]
  return arr[n-1]
};

递归

不建议用，复杂度太高（指数级），只是因为和递归看起来有点像，所以写出来作为比较

function climbStairs(n: number): number {
  if(n <= 2) return n;
  return climbStairs(n-1) + climbStairs(n-2);
};