[70] 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶

2. 2 阶

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 2 阶

3. 2 阶 + 1 阶

这是入手动态规划方程最基础的两道题型之一，另一题是斐波那契数列。

根据高中学过的数列知识，我们需要将问题求出f(n)与f(n-1)...之间的关系，即得出数列的关于前若干项的通项公式。

我们很容易看出，在这里，f(n) = f(n-1) + f(n-2)。那么我们可以很轻松地将这个公式转变为程序解，即递归写法：

var climbStairs = function(n) {
  if (n === 0 || n === 1) return 1;
  return climbStairs(n - 1) + climbStairs(n - 2);
};

有了递归式，实际上动态规划题里难度最高的部分：状态转移方程，就已经确定了。

状态转移方程： dp[n] = dp[n-1] + dp[n-2]

我们再来确立动态规划的边界值。很显然，这里的边界值dp[0]和dp[1]（即爬楼梯的第0层和第一层的可选择爬法）为1。

之后我们就很容易得出改题的动态规划解法了。

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

同时我们可以注意到，改题状态转移方程只依赖f(n-1)与f(n-2)，因此我们不需要建立一整个数组来记住之前遍历得到的所有数据，可以只用两个变量存储每次计算f(n)之前的f(n-1)与f(n-2)的值就能完成最终的计算，这有助于帮我们降低空间复杂度至O(1)。

var climbStairs = function(n) {
  let dp1 = 1;
  let dp2 = 1;
  while (--n) {
    const temp = dp1 + dp2;
    dp2 = dp1;
    dp1 = temp;
  }
  return dp1;
};

function climbStairs(n: number): number {
  if (n === 1) return 1;
  if (n === 2) return 2;
  let prev = 1;
  let cur = 2;
  for (let i = 3; i <= n; i++) {
    const sum = prev + cur;
    prev = cur;
    cur = sum;
  }
  return cur;
}