目錄

70：爬樓梯

題目要求：

解題思路：（類似斐波那契數(shù)）

遞歸解法：

非遞歸解法：

126：斐波那契數(shù)

題目要求：

解題思路：

遞歸解法：

非遞歸解法：

都看到這了，點(diǎn)個(gè)贊再走唄，謝謝謝謝謝！！！

---

70：爬樓梯

題目要求：

解題思路：（類似斐波那契數(shù)）

遞歸解法：

由題可知，每次可以爬1個(gè)或者2個(gè)臺(tái)階，假如有n個(gè)臺(tái)階，會(huì)有多少種走法？那么我們就想，第一次爬一個(gè)臺(tái)階，那方法數(shù)就是爬這一次臺(tái)階加上剩下n-1個(gè)臺(tái)階的走法，爬兩個(gè)臺(tái)階，那方法數(shù)就是爬完這兩個(gè)臺(tái)階再加上剩下n-2個(gè)臺(tái)階的走法，很容易就想到遞歸的解法了，而使用遞歸我們要找到終止條件，也要寫出遞歸公式

但是這么遞歸的時(shí)間復(fù)雜度很高，LeetCode上通過(guò)不了，會(huì)有很多重復(fù)計(jì)算的斐波那契數(shù)，我們可以用HashMap來(lái)解題，每次往下找之前都記錄一下map里面有沒(méi)有n這個(gè)斐波那契數(shù)，有就不用繼續(xù)往下找了，直接返回這個(gè)斐波那契數(shù)，沒(méi)有就繼續(xù)往下找，有了HashMap的引用，我們時(shí)間復(fù)雜度就變成了O(N)，在LeetCode上也就能通過(guò)了。

遞歸公式如下：

代碼如下：

class Solution {HashMap<Integer, Integer> hashmap = new HashMap<>();public int climbStairs(int n) {if(n == 1) {return 1;}if(n == 2) {return 2;}//每次遞歸都判斷map有沒(méi)有n個(gè)臺(tái)階爬樓梯方法數(shù)，沒(méi)有算出當(dāng)前n階臺(tái)階的方法數(shù)，放進(jìn)map里，放進(jìn)map里后就不用繼續(xù)往下遞歸了，直接返回這個(gè)方法數(shù)，因?yàn)閔ashmap已經(jīng)存了n階臺(tái)階的方法數(shù)了；有就不用繼續(xù)遞歸了，直接返回n臺(tái)階的方法數(shù)if(hashmap.get(n) != null) {return hashmap.get(n);} else {int result = climbStairs(n - 1) + climbStairs(n - 2);hashmap.put(n, result);return result;}}
}

非遞歸解法：

從此圖我們可以看出，要求n的斐波那契數(shù)，必須求前一個(gè)和前兩個(gè)的斐波那契數(shù)，也就是上圖的公式，非遞歸的解法，我們就用循環(huán)來(lái)解決，從下至上來(lái)求n的斐波那契數(shù)，我們定義一個(gè)pre和prePre變量來(lái)記錄前一個(gè)和前兩個(gè)的斐波那契數(shù)，result來(lái)記錄n的斐波那契數(shù)，每循環(huán)一次都要更改pre和prePre的下標(biāo)，時(shí)間復(fù)雜度為O(N).

代碼如下：

 public int climbStairs(int n) {//非遞歸思想if(n == 1) {return 1;}if(n == 2) {return 2;}int result = 0;int pre = 2;int prePre = 1;for(int flg = 3; flg <= n; flg++) {result = pre + prePre;//pre和prePre都要往前推prePre = pre;pre = result;}return result;}

126：斐波那契數(shù)

題目要求：

解題思路：

? ? ? ? 這題和爬樓梯思路一樣，解法也一樣，遞歸和非遞歸也一樣，不過(guò)他的遞歸公式和結(jié)束條件和爬樓梯不一樣，公式如下圖：

遞歸思路：因?yàn)檫f歸會(huì)重復(fù)計(jì)算很多次，所以我們可以用一個(gè)HashMap來(lái)記錄n的斐波那契數(shù)，每遞歸一次都判斷map里面有沒(méi)有n的斐波那契數(shù)，有就不用繼續(xù)往下遞歸了，直接返回這個(gè)斐波那契數(shù)，沒(méi)有就往下遞歸，把1后面的斐波那契數(shù)列都記錄在map中，這樣時(shí)間復(fù)雜度就是O(N)了，LeetCode也能通過(guò)。

非遞歸思路：用循環(huán)，從下至上，求得每個(gè)斐波那契數(shù)，我們定義result放n的斐波那契數(shù)，pre放n的前一個(gè)斐波那契數(shù)，prePre放n的前兩個(gè)斐波那契數(shù)，每循環(huán)一次都要更新一次pre和prePre的下標(biāo)，往上走。

遞歸解法：

代碼如下：

 Map<Integer, Integer> map = new HashMap<>();public int fib(int n) {if(n == 0 || n == 1) {return n;}if(map.containsKey(n)) {return map.get(n);}//n的斐波那契數(shù)不在map里int result = (fib(n - 1) + fib(n - 2)) % 1000000007;//int result = (fib(n - 1) + fib(n - 2));map.put(n, result);return result;}

非遞歸解法：

 public int fib(int n) {//非遞歸if(n == 0 || n == 1) {return n;}int result = 0;int pre = 1;int prePre = 0;for(int i = 2; i <= n; i++) {result = (pre + prePre) % 1000000007;prePre = pre;pre = result;}return result;}

---

都看到這了，點(diǎn)個(gè)贊再走唄，謝謝謝謝謝！！！