题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

示例

输入

3

返回值

4

源代码

思路：
我们根据正常跳台阶的做法，可以推断出：
如果上一步跳1步到达第n个台阶的，那么就是f[n-1]的方法数
如果上一步是跳2步到达第n个台阶的，那么就是f[n-2]的方法数
…
如果上一步是跳n步到达第n个台阶的，那么就是f[0]的方法数

这道题还有一个踩坑点就是他可以直接跳n阶，所以有一个第0阶，而且f[0]=1.

我们因此可以很容易的得到递推式为：
f[n]=f[n-1]+f[n-2]+…+f[2]+f[1]+f[0]

class Solution {
public:
    int jumpFloorII(int n) {
	    if (n==0 || n==1) return 1;
	    vector<int> f(n+1, 0);
	    f[0] = f[1] = 1;
	    for (int i=2; i<=n; ++i) {
	        for (int j=0; j<i; ++j) {
	            f[i] += f[j];
	        }
	    }
	    return f[n];
	}
};

在这里，我们根据上面的递推式，
f[n-1]=f[n-2]+…+f[2]+f[1]+f[0],
所以f[n]=2*f[n-1]
继续优化后的代码为：

int jumpFloorII(int n) {
    if (n==0 || n==1) return 1;
    int a = 1, b;
    for (int i=2; i<=n; ++i) {
        b = a * 2;
        a = b;
    }
    return b;
}