java非递归解法
斐波那契数列
http://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3
一开始可能会有人想开辟一个长度为n的数组f[n],但会浪费掉前面很多的空间,根据斐波那契数列计算公式 可知,只需要一个长度为3的数组即可存储需要用到数据,分别用来记录f(n-2), f(n-1), f(n),而 通过取余f(n%3)把前面第三个值即f(n-3)覆盖,就能记录下第n个值了
public class Solution { public int Fibonacci(int n) { int[] f = new int[3]; f[0] = 0; f[1] = 1; for(int i=2; i<=n; ++i){ f[i%3] = f[(i-1)%3] + f[(i-2)%3]; //覆盖第f(i-3)个值 } return f[n%3]; } }