动态规划

这一个基本的动态规划的题，我们需要对问题进行拆分 假设我们处于x层，在合法的情况下，我们考虑，那些可能是结果集。 可以发现，答案是类似：

		aaaaa...aaaax  路径
        bbbbb...aaaax
        

似乎很不好考虑（最后都是在x层），我们不妨考虑最后一步，也就是如何到x的，在合法的情况下，到x的途径有两种，即x-1而来，x-2而来，于是可以得出：f[n] = f[n - 1] + f[n - 2];

于是得出了出版的答案：可以ac

public class Solution {
    int f[] = new int[41];
    public int jumpFloor(int target) {
        f[0] = 1;
        f[1] = 1;
        for(int i = 2;i <= target;i++){
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[target];
    }
}

但是题目要求空间复杂度为O(1),于是继续分析，我们发现，当前层的结果集只和上一层和上上一层，所以我们直接维护遍历记录即可

public class Solution {
    public int jumpFloor(int target) {
        int a = 1;
        int b = 1;
        for(int i = 2;i <= target;i++){
            int tmp = b;
            b = b + a;
            a = tmp;
        }
        return b;
    }
}

最后我们发现数据量很小，不妨打个表（投机取巧）。

public class Solution {
    static int f[] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141};
    public int jumpFloor(int target) {
        return f[target];
    }
}