题解 | 跳台阶

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloor(int number) {

        if (number == 1) {
            return 1;
        }

        if (number == 2) {
            return 2;
        }

        int NminOne = 2;
        int NminTwo = 1;
        int N = 0;
        
        for (int i=3; i<=number; ++i) {
            N = NminOne + NminTwo;
            NminTwo = NminOne;
            NminOne = N;
        }
        return N;
    }
};

转化成fibonacci问题（动态规划）：n级台阶跳法看成n的函数f(n)，当n>2时， f(n) = f(n-1) + f(n-2)；

注意2个点：

1）和fibonacci数列不一样，起点不是f(0)，而是f(1)；

2）要实现时间复杂度O（n)，空间O（1）需要自下往上求，而不是递归的自上往下；

3）循环的边界条件：首先起始是i=3，其次推出条件是i<=number；这点可以根据如下推演：

f(4) = f(3) + f(1)

f(3) = f(2) +f(1)