問題：
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
大意：
你在爬一個樓梯指蚁。需要n節(jié)樓梯到達頂部隙赁。
每次你可以爬一節(jié)或者兩節(jié)樓梯锻狗。你總共有多少種爬到頂部的方法制肮？
思路：
總覺得這個題目小時候做過词疼。一開始想著找找規(guī)律饮怯，按照全程走一個兩節(jié)的蝌衔、兩個兩節(jié)的榛泛、三個兩節(jié)的這么去算，列了一下算式發(fā)現(xiàn)并沒有什么規(guī)律噩斟。曹锨。。
后來想我每到一節(jié)都面臨兩個選擇剃允，即走一節(jié)還是走兩節(jié)沛简，于是想到用遞歸去做齐鲤，不斷返回在某一節(jié)為止走兩節(jié)和走一節(jié)的走法數(shù)量之和。按照這種方法做了之后椒楣，一開始是能夠解決的给郊，測試到了44節(jié)樓梯的時候，就超時了捧灰，看了看答案給出的總走法數(shù)淆九，確實是一個很大的數(shù)字，用遞歸要算的太多了毛俏。
既然往后面的走法去算走不通吩屹，那就往前看，我每來到一節(jié)新的位置的走法數(shù)量都是到上一節(jié)位置的走法數(shù)加上到上兩節(jié)位置的走法數(shù)之和拧抖，一個是走一節(jié)樓梯到當前節(jié)，一個是走兩節(jié)樓梯到當前節(jié)免绿，這樣從第二節(jié)開始去計算（第一節(jié)明顯是一種走法唧席，第二節(jié)開始才可以計算兩節(jié)以前的位置走法數(shù)（即處于0位置時，設其為1）加上一節(jié)以前的位置走法數(shù)（即處于1位置時嘲驾，設其為1）淌哟。）走到第二節(jié)的走法之和，慢慢算到最后一層辽故。這里用一個數(shù)組去計算每一層的走法數(shù)徒仓。當然如果要節(jié)省空間也可以就用三個變量，只是每次去改變其值就可以了誊垢。
代碼（Java）：
public class Solution {
public int climbStairs(int n) {
int[] result = new int[n+1];
result[0] = 1;
result[1] = 1;
for (int i = 2; i <= n; i++) {
result[i] = result[i-1] + result[i-2];
}
return result[n];
}
}
代碼（C++）
三個變量輪換記錄：
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
else if (n == 2) return 2;
int a = 1, b = 2;
int i = 3;
int res = 0;
while (i <= n) {
res = a + b;
a = b;
b = res;
i ++;
}
return res;
}
};
合集：https://github.com/Cloudox/LeetCode-Record
