70-爬樓梯

CompileYouth 發布于2019-08-19 11:05 / 662人閱讀

摘要：前言最近在練習動態規劃的題目，然后就隨便選擇了一道簡單的題目爬樓梯，題目如下假設你正在爬樓梯。斐波那契數列爬樓梯實現代碼爬樓梯

前言

最近在練習動態規劃的題目，然后就隨便選擇了一道簡單的題目——爬樓梯，題目如下：

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

示例 1：

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

示例 2：

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

解題思路

這道題目雖然分類是動態規劃，但是實際上就是個斐波那契數列，不過是一個當入參為n時，需對應的是斐波那契數列的f(n+1)。
斐波那契數列：

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

實現代碼

    /**
     * 爬樓梯
     * @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;
        }
    }

云服務器 GPU云服務器爬樓梯樓梯兔子上樓梯c語言 70cdn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76982.html

【Leetcode】70. 爬樓梯

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

raoyi 2019-07-24 10:49 評論0 收藏0
【Leetcode】70. 爬樓梯

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

187J3X1 2019-06-26 17:49 評論0 收藏0
【Leetcode】70. 爬樓梯

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

wow_worktile 2019-07-25 14:26 評論0 收藏0
LeetCode 之 JavaScript 解答第70題 —— 爬樓梯（Climbing Stair

摘要：小鹿題目假設你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數。算法思路二種解決思路，第一利用遞歸第二利用動態規劃。就是因為有了重復元素的計算，導致了時間復雜度成指數的增長。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿題目：Climbing Stairs You a...

chemzqm 2019-08-23 16:55 評論0 收藏0