[[429460]]

本文轉(zhuǎn)載自微信公眾號「JS每日一題」，作者灰灰。轉(zhuǎn)載本文請聯(lián)系JS每日一題公眾號。

一、貪心算法

貪心算法，又稱貪婪算法，是算法設(shè)計中的一種思想

其期待每一個階段都是局部最優(yōu)的選擇，從而達到全局最優(yōu)，但是結(jié)果并不一定是最優(yōu)的

舉個零錢兌換的例子，如果你有1元、2元、5元的錢幣數(shù)張，用于兌換一定的金額，但是要求兌換的錢幣張數(shù)最少

如果現(xiàn)在你要兌換11元，按照貪心算法的思想，先選擇面額最大的5元錢幣進行兌換，那么就得到11 = 5 + 5 + 1 的選擇，這種情況是最優(yōu)的

但是如果你手上錢幣的面額為1、3、4，想要兌換6元，按照貪心算法的思路，我們會 6 = 4 + 1 + 1這樣選擇，這種情況結(jié)果就不是最優(yōu)的選擇

從上面例子可以看到，貪心算法存在一些弊端，使用到貪心算法的場景，都會存在一個特性：

一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法

至于是否選擇貪心算法，主要看是否有如下兩大特性：

• 貪心選擇：當(dāng)某一個問題的整體最優(yōu)解可通過一系列局部的最優(yōu)解的選擇達到，并且每次做出的選擇可以依賴以前做出的選擇，但不需要依賴后面需要做出的選擇
• 最優(yōu)子結(jié)構(gòu)：如果一個問題的最優(yōu)解包含其子問題的最優(yōu)解，則此問題具備最優(yōu)子結(jié)構(gòu)的性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題是否可以用貪心算法求解的關(guān)鍵所在

二、回溯算法

回溯算法，也是算法設(shè)計中的一種思想，是一種漸進式尋找并構(gòu)建問題解決方式的策略

回溯算法會先從一個可能的工作開始解決問題，如果不行，就回溯并選擇另一個動作，知道將問題解決

使用回溯算法的問題，有如下特性：

• 有很多路，例如一個矩陣的方向或者樹的路徑
• 在這些的路里面，有死路也有生路，思路即不符合題目要求的路，生路則符合
• 通常使用遞歸來模擬所有的路

常見的偽代碼如下：

result = [] 
function backtrack(路徑, 選擇列表): 
  if 滿足結(jié)束條件: 
    result.add(路徑) 
  return 
 
  for 選擇 of 選擇列表: 
    做選擇 
    backtrack(路徑, 選擇列表) 
    撤銷選擇 

重點解決三個問題：

• 路徑：也就是已經(jīng)做出的選擇
• 選擇列表
• 結(jié)束條件

例如經(jīng)典使用回溯算法為解決全排列的問題，如下：

一個不含重復(fù)數(shù)字的數(shù)組 nums ，我們要返回其所有可能的全排列，解決這個問題的思路是：

• 用遞歸模擬所有的情況
• 遇到包含重復(fù)元素的情況則回溯
• 收集到所有到達遞歸終點的情況，并返回、

用代碼表示則如下：

var permute = function(nums) { 
    const res = [], path = []; 
    backtracking(nums, nums.length, []); 
    return res; 
     
    function backtracking(n, k, used) { 
        if(path.length === k) { 
            res.push(Array.from(path)); 
            return; 
        } 
        for (let i = 0; i < k; i++ ) { 
            if(used[i]) continue; 
            path.push(n[i]); 
            used[i] = true; // 同支 
            backtracking(n, k, used); 
            path.pop(); 
            used[i] = false; 
        } 
    } 
}; 

三、總結(jié)

前面也初步了解到分而治之、動態(tài)規(guī)劃，現(xiàn)在再了解到貪心算法、回溯算法

其中關(guān)于分而治之、動態(tài)規(guī)劃、貪心策略三者的求解思路如下：

其中三者對應(yīng)的經(jīng)典問題如下圖：

參考文獻

https://zh.wikipedia.org/wiki/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95

https://leetcode-cn.com/problems/permutations/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-mfrp/

https://cloud.tencent.com/developer/article/1767046