题目：

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

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

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

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;
    }
}

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