#科學燃計劃#
分治：分而治之，先解決子問題算法時間復雜性分析，再將子問題的解合并求出原問題。
貪心：一條路走到黑，選擇當下局部最優的路線，沒有后悔藥。
回溯：一條路走到黑，手握后悔藥，可以無數次重來。(英雄聯盟艾克大招無冷卻)。
動態規劃：上帝視角，手握無數平行宇宙的歷史存檔，同時發展出無數個未來。
初學者一聽到算法思想，就會覺得它們高深莫測，只能望而卻步。
但如果你看過《事實》這本書，你就不會被大腦中的慣性思維所影響。 只要我們理解算法思想的關鍵點，多做題練習并加深理解記憶。其實算法思想就像切菜一樣簡單。
上一篇算法系列專欄中我們搞明白了遞歸。其實遞歸這種編程技巧是很多算法的基礎。
比如本文講到的這幾種算法思想，大部分都是基于遞歸思想基礎上的。
一句話理解四種算法思想
分治：分而治之，先解決子問題算法時間復雜性分析，再將子問題的解合并求出原問題。
貪心：一條路走到黑，選擇當下局部最優的路線，沒有后悔藥。
回溯：一條路走到黑，手握后悔藥，可以無數次重來。(英雄聯盟艾克大招無冷卻)。
動態規劃：上帝視角，手握無數平行宇宙的歷史存檔，同時發展出無數個未來。
接下來我們一起庖丁解牛，將這幾種算法思想一鍋燉。
分治算法 and
分治算法思想很大程度上是基于遞歸的，也比較適合用遞歸來實現。顧名思義，分而治之。一般分為以下三個過程：
分解：將原問題分解成一系列子問題。解決：遞歸求解各個子問題，若子問題足夠小，則直接求解。合并：將子問題的結果合并成原問題。
比較經典的應用就是歸并排序 (Merge Sort) 以及快速排序 (Quick Sort) 等。我們來從歸并排序理解分治思想，歸并排序就是將待排序數組不斷二分為規模更小的子問題處理，再將處理好的子問題合并起來。
上代碼。
const?mergeSort?=?function(arr)?{????const?len?=?arr.length;????if?(len?>?1)?{????????//?對半分解????????const?middle?=?Math.floor(len?/?2);????????const?left?=?arr.slice(0,?middle);????????const?right?=?arr.slice(middle,?len);????????let?i?=?0;?????????let?j?=?0;????????let?k?=?0;????????//?分別對左右進行排序????????mergeSort(left);????????mergeSort(right);????????while(i?復雜度分析時間復雜度：O(nlogn)空間復雜度：O(n)動態規劃 真題
70. 爬樓梯
雖然動態規劃的最終版本 (降維再去維) 大都不是遞歸，但解題的過程還是離開不遞歸的。新手可能會覺得動態規劃思想接受起來比較難，確實，動態規劃求解問題的過程不太符合人類常規的思維方式，我們需要切換成機器思維。
使用動態規劃思想解題，首先要明確動態規劃的三要素。
動態規劃三要素重疊子問題最優子結構狀態轉移方程重疊子問題
切換機器思維，自底向上思考。
爬第 n 階樓梯的方法數量，等于兩部分之和：
爬上 n-1 階樓梯的方法數量爬上 n-2 階樓梯的方法數量最優子結構
子問題的最優解能夠推出原問題的優解。
狀態轉移方程
dp[n] = dp[n-1] + dp[n-2]
具備三要素，確認邊界條件，初始化狀態，開始切菜：
dp[0] = 1dp[1] = 1
const?climbStairs?=?function(n)?{????const?dp?=?[];????dp[0]?=?1;????dp[1]?=?1;????for?(let?i?=?2;?i?<=?n;?i++)?{????????dp[i]?=?dp[i-1]?+?dp[i-2];????}????return?dp[n];};復雜度分析時間復雜度：O(n)空間復雜度：O(n)優化
在此基礎上，我們還可以通過壓縮空間來對算法進行優化。因為 dp[i]只與 dp[i-1] 和 dp[i-2] 有關，沒有必要存儲所有出現過的 dp 項，只用兩個臨時變量去存儲這兩個狀態即可。
const?climbStairs?=?function(n)?{????let?a1?=?1;????let?a2?=?1;????for?(let?i?=?2;?i?<=?n;?i++)?{????????[a1,?a2]?=?[a2,?a1?+?a2];????}????return?a2;}復雜度分析時間復雜度：O(n)空間復雜度：O(1)貪心算法
“
最近某音很火的貪心土味情話
”
“
喂，不是吧。今天喝了脈動啊，吃了果凍啊，但是，還是忍不住對你心動啊。
”
回到算法中，貪心算法是動態規劃算法的一個子集，可以更高效解決一部分更特殊的問題。實際上，用貪心算法解決問題的思路，并不總能給出最優解。因為它在每一步的決策中，選擇目前最優策略，不考慮全局是不是最優。
真題
455. 分發餅干
思路
貪心算法+雙指針求解。
給一個孩子的餅干應當盡量小并且能滿足孩子，大的留來滿足胃口大的孩子因為胃口小的孩子最容易得到滿足，所以優先滿足胃口小的孩子需求按照從小到大的順序使用餅干嘗試是否可滿足某個孩子當餅干 j >= 胃口 i 時，餅干滿足胃口，更新滿足的孩子數并移動指針 i++ j++ res++當餅干 j < 胃口 i 時，餅干不能滿足胃口，需要換大的 j++關鍵點
將需求因子 g 和 s 分別從小到大進行排序，使用貪心思想配合雙指針，每個餅干只嘗試一次，成功則換下一個孩子來嘗試。
復雜度分析時間復雜度：O(nlogn)空間復雜度：O(1)
const?findContentChildren?=?function?(g,?s)?{????g?=?g.sort((a,?b)?=>?a?-?b);????s?=?s.sort((a,?b)?=>?a?-?b);????let?gi?=?0;?//?胃口值????let?sj?=?0;?//?餅干尺寸????let?res?=?0;????while?(gi?=?g[gi])?{????????????gi++;????????????sj++;????????????res++;????????}?else?{????????????sj++;????????}????}????return?res;};回溯算法
回溯算法本質上就是枚舉，使用摸著石頭過河的查找策略，還可以通過剪枝少走冤枉路。
真題
17.電話號碼的字母組合
思路
使用回溯法進行求解，回溯是一種通過窮舉所有可能情況來找到所有解的算法。如果一個候選解最后被發現并不是可行解，回溯算法會舍棄它，并在前面的一些步驟做出一些修改，并重新嘗試找到可行解。究其本質，其實就是枚舉。
如果沒有更多的數字需要被輸入，說明當前的組合已經產生。
如果還有數字需要被輸入：
遍歷下一個數字所對應的所有映射的字母將當前的字母添加到組合最后，也就是 str + tmp[r]關鍵點
在for循環中調用遞歸。
復雜度分析
N+M 是輸入數字的總數
時間復雜度：O(3^N * 4^M)空間復雜度：O(3^N * 4^M)
const?letterCombinations?=?function?(digits)?{????if?(!digits)?{????????return?[];????}????const?len?=?digits.length;????const?map?=?new?Map();????map.set('2',?'abc');????map.set('3',?'def');????map.set('4',?'ghi');????map.set('5',?'jkl');????map.set('6',?'mno');????map.set('7',?'pqrs');????map.set('8',?'tuv');????map.set('9',?'wxyz');????const?result?=?[];????function?generate(i,?str)?{????????if?(i?==?len)?{????????????result.push(str);????????????return;????????}????????const?tmp?=?map.get(digits[i]);????????for?(let?r?=?0;?r?