有一樓梯共m級逐样，剛開始時灭返，你在第一級，若每次只能跨上一級或者二級涵叮，要走上m級惭蹂，共有多少種走法？（注：規(guī)定從一級到一級有0種走法）
我們用 int countWays(int n) 函數(shù)來求解割粮。這里的n代表樓梯級數(shù)盾碗，返回值表示上樓的方式數(shù)。
由于每次只能上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);
}
}
這里，很顯然幽歼，當(dāng)n為1時朵锣，只有一種走法；當(dāng)n為2時甸私，有兩種走法诚些。
這是典型的斐波那契數(shù)列，用這種算法會超時。另外诬烹，砸烦。在計算countWays(n - 1)時，會計算countWays(n - 2)和countWays(n - 3)绞吁；在計算countWays(n - 2)時幢痘，會計算countWays(n - 3)和countWays(n - 4)。以此類推家破，中間有大量的重復(fù)計算颜说。
因此我們采用動態(tài)規(guī)劃的方式來對算法進(jìn)行改造：
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];
}
