來自網易的一道看似簡單的筆試題

題目：要求以線性時間復雜度實現斐波那契數列。

1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89， 。。。。。。

?

眾所周知的斐波那契實現方式為遞歸實現：

      int feb1(int n) {
	t1++;
	if(n == 0 || n == 1) return 1;
	return feb1(n-1) + feb1(n-2);
}
    

當n=25時， 迭代次數為242785 。

關于其復雜度的解釋比較麻煩，詳見 http://www.cnblogs.com/python27/archive/2011/12/09/2282486.html

至今看了公開課視頻后，才有所感悟，采用動態規劃后，其復雜度直接下降到線性，迭代次數為49 。

?

      int a[1000] = {0};
int feb2(int n) {
	t2++;
	if(n == 0 || n == 1) return 1;
	if(a[n] != 0) return a[n];
	else a[n] = feb2(n-1) + feb2(n-2);
	return a[n];
}
    

?