這篇文章主要介紹“C++怎么解決爬樓梯問題”，在日常操作中，相信很多人在C++怎么解決爬樓梯問題問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++怎么解決爬樓梯問題”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)站制作、成都做網(wǎng)站、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)大冶,十年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

爬樓梯問題

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

這篇博客最開始名字叫做爬梯子問題，總是有童鞋向博主反映移動端打不開這篇博客，博主覺得非常奇怪，自己也試了一下，果然打不開。心想著是不是這個博客本身有問題，于是想再開一個相同的帖子，結(jié)果還是打不開，真是見了鬼了。于是博主換了個名字，結(jié)果居然打開了？！進(jìn)經(jīng)過排查后發(fā)現(xiàn)，原來是“爬梯子”這三個字是敏感詞，放到標(biāo)題里面，博客就被屏蔽了，我也真是醉了，完全是躺槍好么，無奈之下，只好改名為爬樓梯問題了 -。-|||。

這個爬梯子問題最開始看的時候沒搞懂是讓干啥的，后來看了別人的分析后，才知道實際上跟斐波那契數(shù)列非常相似，假設(shè)梯子有n層，那么如何爬到第n層呢，因為每次只能爬1或2步，那么爬到第n層的方法要么是從第 n-1 層一步上來的，要不就是從 n-2 層2步上來的，所以遞推公式非常容易的就得出了：dp[n] = dp[n-1] + dp[n-2]。 由于斐波那契額數(shù)列的求解可以用遞歸，所以博主最先嘗試了遞歸，拿到 OJ 上運行，顯示 Time Limit Exceeded，就是說運行時間超了，因為遞歸計算了很多分支，效率很低，這里需要用動態(tài)規(guī)劃 (Dynamic Programming) 來提高效率，代碼如下：

C++ 解法一：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;
        vector<int> dp(n);
        dp[0] = 1; dp[1] = 2;
        for (int i = 2; i < n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp.back();
    }
};

Java 解法一：

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        int[] dp = new int[n];
        dp[0] = 1; dp[1] = 2;
        for (int i = 2; i < n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}

我們可以對空間進(jìn)行進(jìn)一步優(yōu)化，只用兩個整型變量a和b來存儲過程值，首先將 a+b 的值賦給b，然后a賦值為原來的b，所以應(yīng)該賦值為 b-a 即可。這樣就模擬了上面累加的過程，而不用存儲所有的值，參見代碼如下：

C++ 解法二：

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        while (n--) {
            b += a;
            a = b - a;
        }
        return a;
    }
};

Java 解法二：

public class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1;
        while (n-- > 0) {
            b += a; 
            a = b - a;
        }
        return a;
    }
}

雖然前面說過遞歸的寫法會超時，但是只要加上記憶數(shù)組，那就不一樣了，因為記憶數(shù)組可以保存計算過的結(jié)果，這樣就不會存在重復(fù)計算了，大大的提高了運行效率，其實遞歸加記憶數(shù)組跟迭代的 DP 形式基本是大同小異的，參見代碼如下：

C++ 解法三：

class Solution {
public:
    int climbStairs(int n) {
        vector<int> memo(n + 1);
        return helper(n, memo);
    }
    int helper(int n, vector<int>& memo) {
        if (n <= 1) return 1;
        if (memo[n] > 0) return memo[n];
        return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    }
};

Java 解法三：

public class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return helper(n, memo);
    }
    public int helper(int n, int[] memo) {
        if (n <= 1) return 1;
        if (memo[n] > 0) return memo[n];
        return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    }
}

論壇上還有一種分治法 Divide and Conquer 的解法，用的是遞歸形式，可以通過，但是博主沒有十分理解，希望各位看官大神可以跟博主講一講～

C++ 解法四：

public class Solution {
    public int climbStairs(int n) {
        if(n <= 1) return 1;       
        return climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1);
    }
}

Java 解法四：

public class Solution {
    public int climbStairs(int n) {
        if(n <= 1) return 1;       
        return climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1);
    }
}

其實斐波那契數(shù)列是可以求出通項公式的，推理的過程請參見 知乎上的這個貼子，那么有了通項公式后，直接在常數(shù)級的時間復(fù)雜度范圍內(nèi)就可以求出結(jié)果了，參見代碼如下：

C++ 解法五：

class Solution {
public:
    int climbStairs(int n) {
        double root5 = sqrt(5);
        return (1 / root5) * (pow((1 + root5) / 2, n + 1) - pow((1 - root5) / 2, n + 1));
    }
};

Java 解法五：

public class Solution {
    public int climbStairs(int n) {
        double root5 = Math.sqrt(5);
        double res =  (1 / root5) * (Math.pow((1 + root5) / 2, n + 1) - Math.pow((1 - root5) / 2, n + 1));
        return (int)res;
    }
}

到此，關(guān)于“C++怎么解決爬樓梯問題”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>

標(biāo)題名稱：C++怎么解決爬樓梯問題
轉(zhuǎn)載來于：http://chinadenli.net/article40/giogho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計公司、外貿(mào)網(wǎng)站建設(shè)、用戶體驗、電子商務(wù)、手機網(wǎng)站建設(shè)、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)