有一楼梯共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];
}
