题目:

写出一个函数,输入 n,求斐波那契数列的第 n 项。斐波那契数列的定义如下:
f(n) =

  1. 0, n = 0
  2. 1, n = 1
  3. f(n - 1) + f(n - 2), n > 1

斐波那契数列相对来说是比较熟悉的一个概念,主要思路是当前项的值为前两项的值之和,所以只需要一步一步保存并计算之前的值即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int Fibonacci(int n) {
int first = 0, second = 1, i = 0;
while (i < n){
second = first + second;
first = second - first;
i ++;
}
return first;
}
}

时间复杂度为O(n),空间复杂度为O(1)

问题扩展

一只青蛙一次可以跳上一级台阶,也可以跳上两级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

这个问题可以逐步分解,考察第 i 级台阶,明显第 i 级台阶有两种跳法,分别是从第 i - 1 和 i - 2 级台阶跳上来,所以跳上 i 级台阶的跳法应该是 i - 1 级和 i - 2 级台阶跳法的总和,于是有f(i) = f(i - 1) + f(i - 2),其实就是斐波那契数列。代码如下

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int JumpFloor(int target) {
int first = 1, second = 1, i = 0;
while (i < target){
second = first + second;
first = second - first;
i ++;
}
return first;
}
}

其实这个题目有一点动态规划的意思,不过是简化的版本,不需要存储所有状态,只需要前两个即可。动态规划则可能需要存储所有状态的数据,用以计算之后的状态。