成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

70-爬樓梯

CompileYouth / 664人閱讀

摘要：前言最近在練習(xí)動(dòng)態(tài)規(guī)劃的題目，然后就隨便選擇了一道簡(jiǎn)單的題目爬樓梯，題目如下假設(shè)你正在爬樓梯。斐波那契數(shù)列爬樓梯實(shí)現(xiàn)代碼爬樓梯

前言

最近在練習(xí)動(dòng)態(tài)規(guī)劃的題目，然后就隨便選擇了一道簡(jiǎn)單的題目——爬樓梯，題目如下：

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。


示例 1：


輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1.  1 階 + 1 階
2.  2 階


示例 2：


輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階
解題思路

這道題目雖然分類是動(dòng)態(tài)規(guī)劃，但是實(shí)際上就是個(gè)斐波那契數(shù)列，不過(guò)是一個(gè)當(dāng)入?yún)閚時(shí)，需對(duì)應(yīng)的是斐波那契數(shù)列的f(n+1)。
斐波那契數(shù)列：

f(0)=0
f(1)=1
f(2)=f(1)+f(0)=1
f(3)=f(2)+f(1)=2
f(4)=f(3)+f(2)=3
f(5)=f(4)+f(3)=5
f(6)=f(5)+f(4)=8
f(7)=f(6)+f(5)=13

爬樓梯:

c(0)=f(0)=0
c(1)=f(0)+f(1)=f(2)=1
c(2)=f(1)+f(2)=f(3)=2
c(3)=f(2)+f(3)=f(4)=3
c(4)=f(3)+f(4)=f(5)=5
c(5)=f(4)+f(5)=f(6)=8
c(6)=f(5)+f(6)=f(7)=13
實(shí)現(xiàn)代碼 
    /**
     * 爬樓梯
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else{
            int f1 = 1;
            int f2 = 2;
            int result = 0;
            for (int i = 3; i <=n; ++i){
                result=f1+f2;
                f1 = f2;
                f2 = result;
            }
            return result;
        }
    }

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76982.html

相關(guān)文章

  • 【Leetcode】70. 爬樓梯

    摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個(gè)題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來(lái)就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。 每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個(gè)正整數(shù)。 示...

    raoyi 評(píng)論0 收藏0

  • 【Leetcode】70. 爬樓梯

    摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個(gè)題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來(lái)就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。 每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個(gè)正整數(shù)。 示...

    187J3X1 評(píng)論0 收藏0

  • 【Leetcode】70. 爬樓梯

    摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個(gè)題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來(lái)就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。 每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個(gè)正整數(shù)。 示...

    wow_worktile 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第70題 —— 爬樓梯（Climbing Stair

    摘要：小鹿題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。算法思路二種解決思路，第一利用遞歸第二利用動(dòng)態(tài)規(guī)劃。就是因?yàn)橛辛酥貜?fù)元素的計(jì)算，導(dǎo)致了時(shí)間復(fù)雜度成指數(shù)的增長(zhǎng)。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 題目：Climbing Stairs You a...

    chemzqm 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

CompileYouth

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<