來自網(wǎng)易的一道看似簡單的筆試題

題目：要求以線性時(shí)間復(fù)雜度實(shí)現(xiàn)斐波那契數(shù)列。

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

?

眾所周知的斐波那契實(shí)現(xiàn)方式為遞歸實(shí)現(xiàn)：

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

當(dāng)n=25時(shí)， 迭代次數(shù)為242785 。

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

至今看了公開課視頻后，才有所感悟，采用動(dòng)態(tài)規(guī)劃后，其復(fù)雜度直接下降到線性，迭代次數(shù)為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];
}
    

?