題目

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

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

思路

首先我們先列出來前幾個臺階的答案從第一個開始：1，2，3，5。前幾個臺階我們比較好想所以可以直接算出來，我們發現這里面是不是有什么規律啊，第三個臺階的答案是一二臺階的和，第四個臺階的答案是二三臺階的和。這是巧合還是規律呢？我們可以再寫后面兩個的答案或者仔細觀察一下題目。
這就是規律不是巧合，為什么呢？題目說了我們每次只能爬一個或兩個臺階那么我們想要爬到第四個臺階是不是只能從第二個一下走兩個臺階到或者從第三個一下走一個臺階到。所以呢想要到第四個臺階我們必須先到第二個或者第三個臺階，他們倆有各有多少種走法相加不就是第四個臺階的走法嗎？所以從第三個臺階開始每層臺階的答案就是前兩層臺階的答案相加，我們假設f(n)是第n層臺階的走法，那么f(n) = f(n-2) + f(n-1)。
那么有了這個方程我們不就可以最底層開始一步一步的算到第n層嗎，不就得到答案了嗎？這道題用到的思想是動態規劃，我們可以發現我們每層得到的數都是這層的最終答案也就是把題目從得到第n層方法轉換為了得到第n-2，第n-1層臺階的答案以此類推最終到第0層。所以既然能從上往下推也就可以從下往上得到答案，這就是動態規劃的思想也就是把一個問題拆成子問題然后通過得到子問題的答案來推得原來問題的答案。而上面那個方程就是轉換方程。

代碼

class Solution {
public:int climbStairs(int n) {// 先得出爬一樓和二樓的值int p = 1;int q = 2;if (n == 1) {return p;} else if (n == 2) {return q;} else {// 從三樓開始// 因為我們一次只能爬一樓或者二樓// 所以從第三層開始每層的方法就等于// 前兩樓的方法的總和int r = 0;for (int i = 3; i <= n; i++) {r = p + q;p = q;q = r;}return r;}}
};