题目：N个台阶，一次可以走一步或者两步，求走这N个台阶有多少种走法
思路：首先，这是一个斐波那契数列的应用，但是，这里我们不直接给出算法，而是给出算法的思路。走到第N个台阶，要么你是从第N-1层走一步到，要么你是从第N-2层走两步到。令走到第N-1层的方法数是an-1，走到第N-2层的方法数是an-2，走到第N层的方法数是an，我们有an=an-1+an-2，这个公式是斐波那契数列的通项公式。我们令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;
}
上述代码有个问题，就是我们会重复多次求解N-2的问题，在求解N-1的时候，我们会求解N-2，在求解N-2的时候，我们还要求解N-2，这就出现了重复，根据DP的解决思路，我们可以设置一张表，我们可用查表的方式进行求解。
代码如下：
#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 << "层数:" << N << endl << "方法数:" << GetNValue(N, vecNValue) << endl;
return 0;
}
另外，尾递归是可以很容易转化成非递归的形式的，读者自行实现
