寫在前沿：本文代碼均使用C語言編寫

Description:

假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數(shù)。

示例 1：

輸入： 2

輸出： 2

解釋： 有兩種方法可以爬到樓頂。

1.? 1 階 + 1 階

2.? 2 階

示例 2：

輸入： 3

輸出： 3

解釋： 有三種方法可以爬到樓頂。

1.? 1 階 + 1 階 + 1 階

2.? 1 階 + 2 階

3.? 2 階 + 1 階

Analysis：

題目看起來比較復(fù)雜，實際上是一類動態(tài)規(guī)劃問題：要上第N階臺階，只有兩種方案：從第N-1階臺階爬1階上去和從第N-2階臺階爬2階上去。而到達第N-1階臺階的方案同樣只有兩個，從第N-2階臺階爬1階和從第N-3階臺階爬2階上去...換句話說，到達第N階臺階的方案等于到達第N-1階的方案和加上到達第N-2階的方案和，所以要到達第N階臺階的動態(tài)規(guī)劃方程為sum(N)=sum(N-1)+sum(N-2)（看著是不是覺得很眼熟？）。當寫出這個方程的時候爬樓梯問題就轉(zhuǎn)換成了求斐波那契數(shù)列，一激動寫個遞歸解決問題，然后運行時間就超時了...遞歸是一類比較不錯的方案，代碼比較精簡，但是重復(fù)運算多，N較大情況下的運行時間一點都不精簡，所以只能改成非遞歸的形式來解決。這類方法個人覺得不是最優(yōu)解，所以其實更想請教請教是否有更好的方案來解決。

完整C代碼：

int climbStairs(int n) {

? ? if (n==1||n==2)

? ? ? ? return n;

? ? else{

? ? ? ? int a=1,b=2,sum;

? ? ? ? for(int i=2;i<n;i++){

? ? ? ? ? ? sum=a+b;

? ? ? ? ? ? a=b;b=sum;

? ? ? ? }

? ? ? ? return sum;

? ? }

//? ? return climbStairs(n-1)+climbStairs(n-2);//遞歸方法

}