斐波拉契数列变形

题目描述

假设你正在爬楼梯。需要 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 阶

解析

其实这道题目是典型的斐波那契数列问题，在一开始，我是按照解决斐波拉契数列问题的解法适用递归，在整体过测试用例的时候发现用时过长，超出时间限制，并且在执行 n= 46的时候内存益处

后面的时候采用动态规划解法，将前一步的step缓存起来，然后再往下执行，会好很多，代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n <= 2) return n;
    let stepOne = 1, stepTwo = 2;
    for (let i = 3; i <= n; i++) {
        let temp = stepOne + stepTwo;
        stepOne = stepTwo;
        stepTwo = temp;
    }
    return stepTwo;
};