问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级，求，该青蛙跳上一个N级台阶总共有多少种跳法？
分析：1级台阶的跳法显然只有一种，2级台阶有两种，对于3级台阶以上N级，可以看成 n 的函数，记为 f(n)，当 n> 2 时，如果第一次跳 1级，此时跳法总数等于后续 n-1 级台阶的跳法数目，记为 f(n-1)，如果第一次跳2级，此时跳法总数等于后续 n-2 级台阶的跳法数目，记为 f(n-2)。所以 总数目即为 f(n)=f(n-1)+f(n-2)，根据这种思路，容易写出算法如下：
public int fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}上面的答案只能算思路正确，代码上仍有优化的余地，上述代码每一次递归都会重复之前的结点，时间复杂度为 O(2^n)，要达到更好的效果，必须转换为迭代方式，每一次计算将当前结果保留下来，以作为下次计算时使用，优化后的时间复杂度为O(n)?
public int fibonacciOn(int n) {
if (n == 1) {
return 1;
}
int f = 1;
int s = 2;
for (int i = 3; i <= n; i++) {
int third = f + s;
f = s;
s = third;
}
return s;
}