LeetCode 70 Climbing Stairs（爬樓梯）（動态規劃）（*）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50514606

翻譯

你正在爬一個樓梯。它需要n步才能到底頂部。

每次你可以爬1步或者2兩步。

那麼你有多少種不同的方法爬到頂部呢？           

原文

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?           

分析

動态規劃基礎題，首先設定3個變量用于轉換：

int dp1 = 1, dp2 = 2, dpWay = 0;           

根據題意，一次隻能是一步或兩步，是以當n等于2時，有兩種走法：1+1，2。

if (n <= 1) return dp1;
if (n == 2) return dp2;           

從3開始，因為可以直接獲得它的步數結果，是以直接寫成：

while ((n--)-2) {
}           

最終裡面的變化方式為：

dpWay = dp1 + dp2;
dp1 = dp2;
dp2 = dpWay;           

上一篇部落格：

LeetCode 206 Reverse Linked List（反轉連結清單）（四步将遞歸改寫成疊代）（*）

，介紹了如何将遞歸改寫成疊代，看過的童鞋應該會覺得非常容易的，那麼這裡再來轉換一次：

int climbStairsIter(int n,  int dpWay,int dp1, int dp2) {
    if (n <= 1) return dp1;
    if (n == 2) return dp2;
    if ((n--) - 2) {
        dpWay = dp1 + dp2;
        dp1 = dp2;
        dp2 = dpWay;
        return climbStairsIter(n, dpWay, dp1, dp2);
    }
    else return dpWay;
}

int climbStairs(int n) {
    return climbStairsIter(n, 0,1,2);
}           

因為這裡的參數涉及到執行前面順序，是以最好還是單獨列出來了，不過這樣看來略不簡潔呐。

代碼

class Solution {
public:
    int climbStairs(int n) {

        int dp1 = 1, dp2 = 2, dpWay = 0;
        if (n <= 1) return dp1;
        if (n == 2) return dp2;

        while ((n--) - 2) {
            dpWay = dp1 + dp2;
            dp1 = dp2;
            dp2 = dpWay;
        }
        return dpWay;
    }
};