斐波那契数列Java实现（递归，动态规划）
斐波那契数列
http://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
递归解法
public class Solution {
public int Fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
} 斐波那契数列性质F(N) = F(N-1) + F(N-2)，所以用递归解决。题目描述从0开始，所以0、1为基准情形。
动态规划
public class Solution {
public int Fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int last = 1;
int nextToLast = 0;
int rs = 1;
for (int i = 2; i <= n; i++) {
rs = last + nextToLast;
nextToLast = last;
last = rs;
}
return rs;
}
} 
