【算法】爬楼梯-动态规划

题目

原题地址：70. 爬楼梯 - 力扣（LeetCode）

解题思路

用动态规划的思想分解问题：n 级台阶的爬法 = n-1级台阶的爬法 + n-2级台阶的爬法。

将 n 级台阶的爬法记为 f(n)，那么 f(n) = f(n-1) + f(n-2)，很明显是一个斐波那契数列。

• 斐波那契数列：

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

climbStairs 函数执行一次，内部执行两次 climbStairs 函数，n 的值与 climbStairs 函数调用次数关系为：$2^0, 2^1, 2^2, 2^3...2^n$，所以时间复杂度为 $O(2^n)$。

时间复杂度：$O(2^n)$

空间复杂度：$O(1)$

• 优化后的斐波那契数列

观察发现上面算法中会出现大量的重复计算，可以将计算结果缓存起来，减少计算次数。

const cache = {
  0: 1,
  1: 1,
};
function climbStairs(n) {
  if (cache[n]) {
    return cache[n];
  }
  cache[n] = climbStairs(n - 1) + climbStairs(n - 2);
  return cache[n];
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

• 用迭代优化

var climbStairs = function (n) {
  let left = 0,
    mid = 0,
    right = 1;
  for (let i = 1; i <= n; i++) {
    left = mid;
    mid = right;
    right = left + mid;
  }
  return right;
};
let result = climbStairs(43);
console.log(result);

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