NC68.跳台阶

class Solution {
public:
    int jumpFloor(int number) {
        // f(1) = 1
        // f(2) = 2
        // f(n) = f(n - 1) + f(n - 2)
        int ans = -1;
        if (number >= 1 && number <= 40) {
            if (number == 1) {
                ans = 1;
            }
            if (number == 2) {
                ans = 2;
            }
            int front = 2, after = 1;
            int tmp;
            for (int i = 3; i <= number; ++i) {
                ans = front + after;
                tmp = front;
                front = ans;
                after = tmp;
            }
        }
        return ans;
    }
};

解题思路：

难点1：重点中的重点，就看能不能总结出递推公式了。第一反应想着能不能通过数学方法得到直接公式，在O(1)的时空复杂度内完成题解，在这上面浪费了时间；

// f(1) = 1
// f(2) = 2
// f(n) = f(n - 1) + f(n - 2)

难点2：即使是总结出递推公式，题目对时空复杂度有着严格的限制，没办法直接用递归去做，最终还是得要靠动态规划并压缩动态空间去解决；

难点3：总结公式的时候，个人认为没有必要去看f(0)的情况，不太好理解，直接看f(1)和f(2)即可；

难点4：用了一个ans变量，代码多了几行，但没有官方给出的答案那么绕，便于理解；

最后，真的很烦动态规划！！！