动态规划2：上台阶问题

有一个共N级的台阶，一次可以走1级或者2级，问从平地上出发到最高点有多少中走法。

分析： 从终点来看，其走法为倒数一级的走法加上倒数两级的走法。

记f(n) 为到第n级台阶的走法，

则得到DP方程： f(n) = f(n-1)+f(n-2);

初始值有：
f(0) = f(1) = 1

发现就是一个菲波那切数列。。

则代码为：

function res(n) {
    let arr = [];
    arr[0] = 1;
    arr[1] = 1;

    for(let i = 2; i<=n; i++) {
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
}

但其实没必要用一个数组来记录之前的值，可以只记录前两个值，将空间复杂度由O(n)降到O(1)， 代码如下：

function result(n) {
    let a= 1;
    let b = 1;
    for(let i = 2; i <= n; i++) {
        [a, b] = [b, a+b];
    }
    return b;
}