查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
import java.util.*;
class Solution {
/**
* @param n: an integer
* @return an integer f(n)
*/
public int fibonacci(int n) {
// write your code here
//定义第n个斐波那契数为sum
int sum = 0;
if(n == 1){
//n为1时直接返回0
sum = 0;
} else if(n == 2){
//n为2时直接返回1
sum = 1;
} else {
//从第三个数开始使用List来处理
ArrayList<Integer>list = new ArrayList<Integer>();
//list中添加第一个斐波那契数
list.add(0);
//list中添加第二个斐波那契数
list.add(1);
//list中添加第n(n>=3)个斐波那契数
for(int i = 3; i <= n; i++){
//第 n 个数是第 n-1 个数和第n-2 个数的和
//因为list下标从0开始，第 i 个数实际为第 i-2 个数和第i-3 个数的和
list.add(list.get(i-2)+list.get(i-3));
//斐波那契数中的第n个数在list中为i-1
sum = list.get(i-1);
}
}
return sum;
}
}
