[[429460]]

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

一、貪心算法

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

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

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

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

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

從上面例子可以看到，貪心算法存在一些弊端，使用到貪心算法的場(chǎng)景，都會(huì)存在一個(gè)特性：

一旦一個(gè)問(wèn)題可以通過(guò)貪心法來(lái)解決，那么貪心法一般是解決這個(gè)問(wèn)題的最好辦法

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

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

二、回溯算法

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

回溯算法會(huì)先從一個(gè)可能的工作開(kāi)始解決問(wèn)題，如果不行，就回溯并選擇另一個(gè)動(dòng)作，知道將問(wèn)題解決

使用回溯算法的問(wèn)題，有如下特性：

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

常見(jiàn)的偽代碼如下：

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

重點(diǎn)解決三個(gè)問(wèn)題：

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

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

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

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

用代碼表示則如下：

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é)

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

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

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

參考文獻(xiàn)

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