讓我們掌聲恭迎動態規劃的始祖——

最基礎的動態規劃，原始方法是維護一個數組，每次記錄到該階梯的方案數量，每次的數量是到上一個階梯的方案數量加上到上上一階梯的方案數量，因為只有兩種走法。

進階可以優化空間復雜度，只記錄兩個數字，因為更之前的數據都用不上了。

我當然是直接寫優化方案——

class Solution {
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;int one=1;int two=2;for(int i=3;i<=n;i++){if(i%2==0) two=one+two;else one=one+two;}return max(one,two);}
};