N个台阶，一次可以走一步或者两步，求走这N个台阶有多少种走法

题目：N个台阶，一次可以走一步或者两步，求走这N个台阶有多少种走法
思路：首先，这是一个斐波那契数列的应用，但是，这里我们不直接给出算法，而是给出算法的思路。走到第N个台阶，要么你是从第N-1层走一步到，要么你是从第N-2层走两步到。令走到第N-1层的方法数是a_n-1，走到第N-2层的方法数是a_n-2，走到第N层的方法数是a_n，我们有a_n=a_n-1+a_n-2，这个公式是斐波那契数列的通项公式。我们令a₁=1,a₂=2，使用迭代算法，可以求得a_n的值。

代码如下：

#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;
}

另外，尾递归是可以很容易转化成非递归的形式的，读者自行实现