這篇文章主要介紹“C++怎么解決爬樓梯問題”,在日常操作中,相信很多人在C++怎么解決爬樓梯問題問題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”C++怎么解決爬樓梯問題”的疑惑有所幫助!接下來,請(qǐng)跟著小編一起來學(xué)習(xí)吧!
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
這篇博客最開始名字叫做爬梯子問題,總是有童鞋向博主反映移動(dòng)端打不開這篇博客,博主覺得非常奇怪,自己也試了一下,果然打不開。心想著是不是這個(gè)博客本身有問題,于是想再開一個(gè)相同的帖子,結(jié)果還是打不開,真是見了鬼了。于是博主換了個(gè)名字,結(jié)果居然打開了?!進(jìn)經(jīng)過排查后發(fā)現(xiàn),原來是“爬梯子”這三個(gè)字是敏感詞,放到標(biāo)題里面,博客就被屏蔽了,我也真是醉了,完全是躺槍好么,無奈之下,只好改名為爬樓梯問題了 -。-|||。
這個(gè)爬梯子問題最開始看的時(shí)候沒搞懂是讓干啥的,后來看了別人的分析后,才知道實(shí)際上跟斐波那契數(shù)列非常相似,假設(shè)梯子有n層,那么如何爬到第n層呢,因?yàn)槊看沃荒芘?或2步,那么爬到第n層的方法要么是從第 n-1 層一步上來的,要不就是從 n-2 層2步上來的,所以遞推公式非常容易的就得出了:dp[n] = dp[n-1] + dp[n-2]。 由于斐波那契額數(shù)列的求解可以用遞歸,所以博主最先嘗試了遞歸,拿到 OJ 上運(yùn)行,顯示 Time Limit Exceeded,就是說運(yùn)行時(shí)間超了,因?yàn)檫f歸計(jì)算了很多分支,效率很低,這里需要用動(dòng)態(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]; } }
我們可以對(duì)空間進(jìn)行進(jìn)一步優(yōu)化,只用兩個(gè)整型變量a和b來存儲(chǔ)過程值,首先將 a+b 的值賦給b,然后a賦值為原來的b,所以應(yīng)該賦值為 b-a 即可。這樣就模擬了上面累加的過程,而不用存儲(chǔ)所有的值,參見代碼如下:
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; } }
雖然前面說過遞歸的寫法會(huì)超時(shí),但是只要加上記憶數(shù)組,那就不一樣了,因?yàn)橛洃洈?shù)組可以保存計(jì)算過的結(jié)果,這樣就不會(huì)存在重復(fù)計(jì)算了,大大的提高了運(yùn)行效率,其實(shí)遞歸加記憶數(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ù)列是可以求出通項(xiàng)公式的,推理的過程請(qǐng)參見 知乎上的這個(gè)貼子,那么有了通項(xiàng)公式后,直接在常數(shù)級(jí)的時(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é)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。