算法习题分析（一）：上台阶

有一楼梯共m级，刚开始时，你在第一级，若每次只能跨上一级或者二级，要走上m级，共有多少种走法？（注：规定从一级到一级有0种走法）

我们用 int countWays(int n) 函数来求解。这里的n代表楼梯级数，返回值表示上楼的方式数。

由于每次只能上1级或2级台阶，我们用递归的思路，很显然，countWays(n) = countWays(n - 1) + countWays(n - 2)，于是就有：

int countWays(int n)
{
    if (n < 3)
    {
        return n;
    }
    else 
    {
        return countWays(n - 1) + countWays(n - 2);
    }
}

这里，很显然，当n为1时，只有一种走法；当n为2时，有两种走法。

这是典型的斐波那契数列，用这种算法会超时。另外，。在计算countWays(n - 1)时，会计算countWays(n - 2)和countWays(n - 3)；在计算countWays(n - 2)时，会计算countWays(n - 3)和countWays(n - 4)。以此类推，中间有大量的重复计算。

因此我们采用动态规划的方式来对算法进行改造：

int countWays(int n)
{
    int dp[] = new int[n];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    if (n > 2)
    {
        for (int i = 3; i < n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
    }
    
    return dp[n - 1];
}