有這么一題

有一個(gè)樓梯總共n個(gè)臺(tái)階，只能往上走,，每次只能上1個(gè),、2個(gè)臺(tái)階，總共有多少種走法,。

小牛的程序員想了想：

解決方案：

dp[n] 表示n個(gè)臺(tái)階的走法,，那么有：

dp[n]=dp[n-1] dp[n-2]；

dp[1]=1;dp[2]=2;

這能難到我,，

大神級(jí)別的程序員來(lái)了

一看,，隨著n數(shù)一直增長(zhǎng)，大量重復(fù)的計(jì)算,，使得復(fù)雜度呈指數(shù)爆炸增長(zhǎng),。

你的遞歸算法,時(shí)間復(fù)雜性，隨著n的增加,，一直爆表,。

看我的,動(dòng)態(tài)規(guī)劃的算法 通過(guò)犧牲空間復(fù)雜度來(lái)?yè)Q取時(shí)間復(fù)雜度的降低。

int stepNumer(int n)
{
 int step1 = 1; 
 int step2 = 2; 
 int stepN = 0;
 for (int i = 2;i < n;i  )
 {
 tempN = step1   step2 ; 
 step1 = step2 ; 
 step2 = tempN ; 
 }
 return n<3?n:tempN;

然后點(diǎn)評(píng)了一下：每個(gè)f(n)只需計(jì)算一次然后記錄下來(lái),，避免了大量重復(fù)的計(jì)算

動(dòng)態(tài)規(guī)劃通過(guò)犧牲空間復(fù)雜度來(lái)?yè)Q取時(shí)間復(fù)雜度的降低,，單大多情況下?tīng)奚侵档玫摹?/p>

小子你的算法不錯(cuò)，不過(guò)還是嫩了點(diǎn),，再好好干幾年,，修行一下。

然后滿意的走了,，一天的心情很是高興,。

突然有一天,，在地?cái)傎u(mài)菜，原本是數(shù)學(xué)系,，出了社會(huì)沒(méi)找到工作,，看到這題，不懂代碼,，隨手寫(xiě)了寫(xiě),。

dp[n]=dp[n-1] dp[n-2]；

dp[1]=1;dp[2]=2;

根據(jù)f(n)=f(n-1) f(n-2),推出特征方程

吸了根煙，長(zhǎng)長(zhǎng)嘆了口氣,，默默的推著三輪車(chē)走了,。

過(guò)了幾天，大牛小?；貋?lái)了,，本想瞻仰一下，自己的代碼,，是何等的牛B,回溫一下當(dāng)時(shí)的成就感,。當(dāng)他們看到

這些公式，什么遞歸,，什么動(dòng)態(tài)規(guī)劃,，在公式面前顯示如此蒼白，只留下一臉忙然~~