題意
題目：爬樓梯
假如你正在爬樓梯，需要 n 階才能到達樓梯頂部.
每次你隻能爬 1 到 2 階.請問你可以有多少種方法到達樓梯頂部.
注意：給定的 n 是一個正整數.
題解
算法及複雜度（0 ms）
本題顯然是一種全局限制性的路徑問題，在一條路徑中某個位置隻能向後走一步或者兩步，也就是說一個位置的上一個位置一定是前一個位置或者前兩個位置.
我們還從最後一個位置開始看，如果要到達位置 n ，此時到達 n 的所有路徑數應該是到達 n - 1 的所有路徑數加上達到 n - 2 的所有路徑上（假設此時 n - 1 和 n - 2 均有意義）.也就是問題轉化為分别求解到達 n - 1 和 n - 2 的路徑數.依次向前遞推.
很容易想到，假設起點到達點n的所有路徑數表示為狀态 dp[n] ，那麼有狀态轉移方程為
dp[n] = dp[n - 1] + dp[ n - 2], n >= 2
.
顯然到達 n - 1 的路徑數并不受 n 之後的點的影響，也就是沒有後效性.滿足使用動态規劃求解的要求.
時間複雜度: O(n). 每個點隻需要計算一次即可.
代碼參見本檔案夾下solution.cpp
算法正确性
舉個例子
// 輸入 n = 5
// 初始化
dp[0] = 1
dp[1] = 1
//繼續求解
dp[2] = dp[1] + dp[0] = 2
dp[3] = dp[1] + dp[2]