摘要:前言最近在練習動態(tài)規(guī)劃的題目,然后就隨便選擇了一道簡單的題目爬樓梯,題目如下假設你正在爬樓梯。斐波那契數(shù)列爬樓梯實現(xiàn)代碼爬樓梯
前言
最近在練習動態(tài)規(guī)劃的題目,然后就隨便選擇了一道簡單的題目——爬樓梯,題目如下:
</>復制代碼
解題思路
這道題目雖然分類是動態(tài)規(guī)劃,但是實際上就是個斐波那契數(shù)列,不過是一個當入?yún)閚時,需對應的是斐波那契數(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
爬樓梯:
實現(xiàn)代碼</>復制代碼
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;
}
}
文章版權歸作者所有,未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/76982.html
摘要:題目假設你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是,狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢? 注意:給定 n 是一個正整數(shù)。 示...
摘要:題目假設你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是,狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢? 注意:給定 n 是一個正整數(shù)。 示...
摘要:題目假設你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是,狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢? 注意:給定 n 是一個正整數(shù)。 示...
摘要:小鹿題目假設你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。算法思路二種解決思路,第一利用遞歸第二利用動態(tài)規(guī)劃。就是因為有了重復元素的計算,導致了時間復雜度成指數(shù)的增長。 Time:2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 題目:Climbing Stairs You a...
閱讀 1652·2023-04-26 02:11
閱讀 2993·2023-04-25 16:18
閱讀 3723·2021-09-06 15:00
閱讀 2639·2019-08-30 15:55
閱讀 1944·2019-08-30 13:20
閱讀 2060·2019-08-26 18:36
閱讀 3136·2019-08-26 11:40
閱讀 2554·2019-08-26 10:11