題目：N個(gè)臺(tái)階颤殴，一次可以走一步或者兩步，求走這N個(gè)臺(tái)階有多少種走法
思路：首先鼻忠，這是一個(gè)斐波那契數(shù)列的應(yīng)用涵但，但是，這里我們不直接給出算法帖蔓，而是給出算法的思路矮瘟。走到第N個(gè)臺(tái)階，要么你是從第N-1層走一步到塑娇，要么你是從第N-2層走兩步到芥永。令走到第N-1層的方法數(shù)是an-1，走到第N-2層的方法數(shù)是an-2钝吮，走到第N層的方法數(shù)是an，我們有an=an-1+an-2，這個(gè)公式是斐波那契數(shù)列的通項(xiàng)公式奇瘦。我們令a1=1,a2=2棘催，使用迭代算法，可以求得an的值耳标。
代碼如下：
#include <iostream>
using namespace std;
int GetNValue(int N)
{
if (N <= 1) return 1;
if (N == 2) return 2;
return GetNValue(N-1) + GetNValue(N-2);
}
int main(int argc, char ** argv)
{
const int N = 10;
cout << N << ":" << GetNValue(N) << endl;
return 0;
}
上述代碼有個(gè)問(wèn)題醇坝，就是我們會(huì)重復(fù)多次求解N-2的問(wèn)題，在求解N-1的時(shí)候次坡，我們會(huì)求解N-2呼猪，在求解N-2的時(shí)候，我們還要求解N-2砸琅，這就出現(xiàn)了重復(fù)宋距，根據(jù)DP的解決思路，我們可以設(shè)置一張表症脂，我們可用查表的方式進(jìn)行求解谚赎。
代碼如下：
#include <iostream>
#include <vector>
using namespace std;
int GetNValue(int N, vector<int> & vecNValue, bool bInit=true)
{
if (N <= 1) return 1;
if (N == 2) return 2;
if (bInit) {
vecNValue.assign(N, 0);
vecNValue[0] = 1;
vecNValue[1] = 2;
}
if (vecNValue[N-1] > 0) return vecNValue[N-1];
vecNValue[N-1] = GetNValue(N-1, vecNValue, false) + GetNValue(N-2, vecNValue, false);
return vecNValue[N-1];
}
int main(int argc, char ** argv)
{
const int N = 10;
vector<int> vecNValue;
cout << "層數(shù):" << N << endl << "方法數(shù):" << GetNValue(N, vecNValue) << endl;
return 0;
}
另外，尾遞歸是可以很容易轉(zhuǎn)化成非遞歸的形式的诱篷，讀者自行實(shí)現(xiàn)
