题解 | #跳台阶扩展问题#

先说这个题目的问题，这个题目没有明确的说明台阶n的取值范围，

1. 没有说明台阶n的下限，没有定义f(0)的取值而且没有对应的测试案例，导致f(0)返回任何值都能通过
2. 没有定义台阶n的上限，这个题目最终是求2的指数级结果，虽然通过参数和返回值的类型可以判断取值范围，但是从严谨的角度还是应该说明一下。

因此这是题目的瑕疵。

但是如果题目给定义了f(0)的值，那么n=0这个案例又是送分的，所以我们姑且认为题目的n取值是正整数，f(0)是我们解题时自己定义的值，与答案无关，我们怎么便于解题怎么定义，直观的看，f(0)似乎取1比较便于理解。

此时：

f[n] = f[n-1] + f[n-2] + ... + f[0]
所以f[n+1] = f[n] + f[n-1] + ... + f[0] = 2f[n]
又f[1]=1,
所以
f[0]=1
f[n]=2^(n-1), 其中n>=1

因此解法一：

public class Solution {
    public int jumpFloorII(int target) {
        if (target == 0 || target == 1) return 1;
        return (1 << (target - 1));
    }
}

实际上编程实践中看到上述操作是非常虚的，毕竟target大一点分分钟就会溢出，但是题目返回值int说明案例也比较简单。

解法二

解法二是排行榜很高的一个答案，这个答案对f[0]的结果就是0，但是也能通过，毕竟题目没有n=0的测试案例，所以这块总觉得是题目不够严谨。

先看原答案（略有调整代码结构，但核心逻辑未变）

public class Solution {
    public int jumpFloorII(int n) {
        int f = 0, s = 0;
        for(int i = 1; i <= n; i++) {
            f = s + 1;
            s += f;
        }
        return f;
    }
}

这个答案也很精简，

f[1] = 1
f[2] = f[1] + 1
...
f[n] = f[n-1] + f[n-2] + ... + 1
假如我们让:
s[0] = 0, 
s[n] = f[n] + f[n-1] + ... + f[1], 其中n >= 1
那么:
f[n] = s[n-1] + 1
s[n] = f[n] + f[n-1] + f[n-2] + ... + f[1] = f[n] + s[n-1]
其中n >= 1.
由此我们得到，
s[0]=0
在n>=1时，有：
f[n] = s[n-1] + 1
s[n] = s[n-1] + f[n]
的递推公式.

这也就是该答案的推理逻辑，但是这个答案假定f[0] = 0或n是正整数，虽然这个边界值意义不大可以自由定义，而且题目也没有具体的说明和测试案例，但是我觉得还是f[0]=1更加直观。因此改动后的如下：

public class Solution {
    public int jumpFloorII(int n) {
        if (n == 0) return 1;
        int f = 0, s = 0;
        for(int i = 1; i <= n; i++) {
            f = s + 1;
            s += f;
        }
        return f;
    }
}