我們號(hào)已經(jīng)寫了 動(dòng)態(tài)規(guī)劃算法，回溯（DFS）算法，BFS 算法，貪心算法，雙指針?biāo)惴?，滑?dòng)窗口算法，現(xiàn)在就差個(gè)分治算法沒寫了，今天來(lái)寫一下，集齊七顆龍珠，就能召喚神龍了~

其實(shí)，我覺得回溯、分治和動(dòng)態(tài)規(guī)劃算法可以劃為一類，因?yàn)樗鼈兌紩?huì)涉及遞歸。

回溯算法就一種簡(jiǎn)單粗暴的算法技巧，說白了就是一個(gè)暴力窮舉算法，比如讓你 用回溯算法求子集、全排列、組合，你就窮舉唄，就考你會(huì)不會(huì)漏掉或者多算某些情況。

動(dòng)態(tài)規(guī)劃是一類算法問題，肯定是讓你求最值的。因?yàn)閯?dòng)態(tài)規(guī)劃問題擁有 最優(yōu)子結(jié)構(gòu)，可以通過狀態(tài)轉(zhuǎn)移方程從小規(guī)模的子問題最優(yōu)解推導(dǎo)出大規(guī)模問題的最優(yōu)解。

分治算法呢，可以認(rèn)為是一種算法思想，通過將原問題分解成小規(guī)模的子問題，然后根據(jù)子問題的結(jié)果構(gòu)造出原問題的答案。這里有點(diǎn)類似動(dòng)態(tài)規(guī)劃，所以說運(yùn)用分治算法也需要滿足一些條件，你的原問題結(jié)果應(yīng)該可以通過合并子問題結(jié)果來(lái)計(jì)算。

其實(shí)這幾個(gè)算法之間界定并沒有那么清晰，有時(shí)候回溯算法加個(gè)備忘錄似乎就成動(dòng)態(tài)規(guī)劃了，而分治算法有時(shí)候也可以加備忘錄進(jìn)行剪枝。

我覺得吧，沒必要過分糾結(jié)每個(gè)算法的定義，定義這東西無(wú)非文學(xué)詞匯而已，反正能把題做出來(lái)你說這是啥算法都行，所以大家還是得多刷題，刷出感覺，各種算法都手到擒來(lái)。

最典型的分治算法就是歸并排序了，核心邏輯如下：

voidsort(int[]nums,intlo,inthi){
intmid=(lo+hi)/2;
/******分******/
//對(duì)數(shù)組的兩部分分別排序
sort(nums,lo,mid);
sort(nums,mid+1,hi);
/******治******/
//合并兩個(gè)排好序的子數(shù)組
merge(nums,lo,mid,hi);
}

「對(duì)數(shù)組排序」是一個(gè)可以運(yùn)用分治思想的算法問題，只要我先把數(shù)組的左半部分排序，再把右半部分排序，最后把兩部分合并，不就是對(duì)整個(gè)數(shù)組排序了嗎？

下面來(lái)看一道具體的算法題。

添加括號(hào)的所有方式

我來(lái)借力扣第 241 題講講什么是分治算法，先看看題目：

簡(jiǎn)單說，就是給你輸入一個(gè)算式，你可以給它隨意加括號(hào)，請(qǐng)你窮舉出所有可能的加括號(hào)方式，并計(jì)算出對(duì)應(yīng)的結(jié)果。

函數(shù)簽名如下：

//計(jì)算所有加括號(hào)的結(jié)果
ListdiffWaysToCompute(Stringinput);

看到這道題的第一感覺肯定是復(fù)雜，我要窮舉出所有可能的加括號(hào)方式，是不是還要考慮括號(hào)的合法性？是不是還要考慮計(jì)算的優(yōu)先級(jí)？

是的，這些都要考慮，但是不需要我們來(lái)考慮。利用分治思想和遞歸函數(shù)，算法會(huì)幫我們考慮一切細(xì)節(jié)，也許這就是算法的魅力吧，哈哈哈。

廢話不多說，解決本題的關(guān)鍵有兩點(diǎn)：

1、不要思考整體，而是把目光聚焦局部，只看一個(gè)運(yùn)算符。

這一點(diǎn)我們前文經(jīng)常提及，比如 手把手刷二叉樹第一期 就告訴你解決二叉樹系列問題只要思考每個(gè)節(jié)點(diǎn)需要做什么，而不要思考整棵樹需要做什么。

說白了，解決遞歸相關(guān)的算法問題，就是一個(gè)化整為零的過程，你必須瞄準(zhǔn)一個(gè)小的突破口，然后把問題拆解，大而化小，利用遞歸函數(shù)來(lái)解決。

2、明確遞歸函數(shù)的定義是什么，相信并且利用好函數(shù)的定義。

這也是前文經(jīng)常提到的一個(gè)點(diǎn)，因?yàn)檫f歸函數(shù)要自己調(diào)用自己，你必須搞清楚函數(shù)到底能干嘛，才能正確進(jìn)行遞歸調(diào)用。

下面來(lái)具體解釋下這兩個(gè)關(guān)鍵點(diǎn)怎么理解。

我們先舉個(gè)例子，比如我給你輸入這樣一個(gè)算式：

1 + 2 * 3 - 4 * 5

請(qǐng)問，這個(gè)算式有幾種加括號(hào)的方式？請(qǐng)?jiān)谝幻胫畠?nèi)回答我。

估計(jì)你回答不出來(lái)，因?yàn)槔ㄌ?hào)可以嵌套，要窮舉出來(lái)肯定得費(fèi)點(diǎn)功夫。

不過呢，嵌套這個(gè)事情吧，我們?nèi)祟悂?lái)看是很頭疼的，但對(duì)于算法來(lái)說嵌套括號(hào)不要太簡(jiǎn)單，一次遞歸就可以嵌套一層，一次搞不定大不了多遞歸幾次。

所以，作為寫算法的人類，我們只需要思考，如果不讓括號(hào)嵌套（即只加一層括號(hào)），有幾種加括號(hào)的方式？

還是上面的例子，顯然我們有四種加括號(hào)方式：

(1) + (2 * 3 - 4 * 5)

(1 + 2) * (3 - 4 * 5)

(1 + 2 * 3) - (4 * 5)

(1 + 2 * 3 - 4) * (5)

發(fā)現(xiàn)規(guī)律了么？其實(shí)就是按照運(yùn)算符進(jìn)行分割，給每個(gè)運(yùn)算符的左右兩部分加括號(hào)，這就是之前說的第一個(gè)關(guān)鍵點(diǎn)，不要考慮整體，而是聚焦每個(gè)運(yùn)算符。

現(xiàn)在單獨(dú)說上面的第三種情況：

(1 + 2 * 3) - (4 * 5)

我們用減號(hào)-作為分隔，把原算式分解成兩個(gè)算式1 + 2 * 3和4 * 5。

分治分治，分而治之，這一步就是把原問題進(jìn)行了「分」，我們現(xiàn)在要開始「治」了。

1 + 2 * 3可以有兩種加括號(hào)的方式，分別是：

(1) + (2 * 3) = 7

(1 + 2) * (3) = 9

或者我們可以寫成這種形式：

1 + 2 * 3 = [9, 7]

而4 * 5當(dāng)然只有一種加括號(hào)方式，就是4 * 5 = [20]。

然后呢，你能不能通過上述結(jié)果推導(dǎo)出(1 + 2 * 3) - (4 * 5)有幾種加括號(hào)方式，或者說有幾種不同的結(jié)果？

顯然，可以推導(dǎo)出來(lái)(1 + 2 * 3) - (4 * 5)有兩種結(jié)果，分別是：

9 - 20 = -11

7 - 20 = -13

那你可能要問了，1 + 2 * 3 = [9, 7]的結(jié)果是我們自己看出來(lái)的，如何讓算法計(jì)算出來(lái)這個(gè)結(jié)果呢？

這個(gè)簡(jiǎn)單啊，再回頭看下題目給出的函數(shù)簽名：

//定義：計(jì)算算式 input 所有可能的運(yùn)算結(jié)果
ListdiffWaysToCompute(Stringinput);

這個(gè)函數(shù)不就是干這個(gè)事兒的嗎？這就是我們之前說的第二個(gè)關(guān)鍵點(diǎn)，明確函數(shù)的定義，相信并且利用這個(gè)函數(shù)定義。

你甭管這個(gè)函數(shù)怎么做到的，你相信它能做到，然后用就行了，最后它就真的能做到了。

那么，對(duì)于(1 + 2 * 3) - (4 * 5)這個(gè)例子，我們的計(jì)算邏輯其實(shí)就是這段代碼：

ListdiffWaysToCompute("(1+2*3)-(4*5)"){
Listres=newLinkedList<>();
/******分******/
Listleft=diffWaysToCompute("1+2*3");
Listright=diffWaysToCompute("4*5");
/******治******/
for(inta:left)
for(intb:right)
res.add(a-b);

returnres;
}

好，現(xiàn)在(1 + 2 * 3) - (4 * 5)這個(gè)例子是如何計(jì)算的，你應(yīng)該完全理解了吧，那么回來(lái)看我們的原始問題。

原問題1 + 2 * 3 - 4 * 5是不是只有(1 + 2 * 3) - (4 * 5)這一種情況？是不是只能從減號(hào)-進(jìn)行分割？

不是，每個(gè)運(yùn)算符都可以把原問題分割成兩個(gè)子問題，剛才已經(jīng)列出了所有可能的分割方式：

(1) + (2 * 3 - 4 * 5)

(1 + 2) * (3 - 4 * 5)

(1 + 2 * 3) - (4 * 5)

(1 + 2 * 3 - 4) * (5)

所以，我們需要窮舉上述的每一種情況，可以進(jìn)一步細(xì)化一下解法代碼：

ListdiffWaysToCompute(Stringinput){
Listres=newLinkedList<>();
for(inti=0;icharc=input.charAt(i);
//掃描算式input中的運(yùn)算符
if(c=='-'||c=='*'||c=='+'){
/******分******/
//以運(yùn)算符為中心，分割成兩個(gè)字符串，分別遞歸計(jì)算
List
left=diffWaysToCompute(input.substring(0,i));
List
right=diffWaysToCompute(input.substring(i+1));
/******治******/
//通過子問題的結(jié)果，合成原問題的結(jié)果
for(inta:left)
for(intb:right)
if(c=='+')
res.add(a+b);
elseif(c=='-')
res.add(a-b);
elseif(c=='*')
res.add(a*b);
}
}
//basecase
//如果res為空，說明算式是一個(gè)數(shù)字，沒有運(yùn)算符
if(res.isEmpty()){
res.add(Integer.parseInt(input));
}
returnres;
}

有了剛才的鋪墊，這段代碼應(yīng)該很好理解了吧，就是掃描輸入的算式input，每當(dāng)遇到運(yùn)算符就進(jìn)行分割，遞歸計(jì)算出結(jié)果后，根據(jù)運(yùn)算符來(lái)合并結(jié)果。

這就是典型的分治思路，先「分」后「治」，先按照運(yùn)算符將原問題拆解成多個(gè)子問題，然后通過子問題的結(jié)果來(lái)合成原問題的結(jié)果。

當(dāng)然，一個(gè)重點(diǎn)在這段代碼：

//basecase
//如果res為空，說明算式是一個(gè)數(shù)字，沒有運(yùn)算符
if(res.isEmpty()){
res.add(Integer.parseInt(input));
}

遞歸函數(shù)必須有個(gè) base case 用來(lái)結(jié)束遞歸，其實(shí)這段代碼就是我們分治算法的 base case，代表著你「分」到什么時(shí)候可以開始「治」。

我們是按照運(yùn)算符進(jìn)行「分」的，一直這么分下去，什么時(shí)候是個(gè)頭？顯然，當(dāng)算式中不存在運(yùn)算符的時(shí)候就可以結(jié)束了。

那為什么以res.isEmpty()作為判斷條件？因?yàn)楫?dāng)算式中不存在運(yùn)算符的時(shí)候，就不會(huì)觸發(fā) if 語(yǔ)句，也就不會(huì)給res中添加任何元素。

至此，這道題的解法代碼就寫出來(lái)了，但是時(shí)間復(fù)雜度是多少呢？

如果單看代碼，真的很難通過 for 循環(huán)的次數(shù)看出復(fù)雜度是多少，所以我們需要改變思路，本題在求所有可能的計(jì)算結(jié)果，不就相當(dāng)于在求算式input的所有合法括號(hào)組合嗎？

那么，對(duì)于一個(gè)算式，有多少種合法的括號(hào)組合呢？這就是著名的「卡特蘭數(shù)」了，最終結(jié)果是一個(gè)組合數(shù)，推導(dǎo)過程稍有些復(fù)雜，我這里就不寫了，有興趣的讀者可以自行搜索了解一下。

其實(shí)本題還有一個(gè)小的優(yōu)化，可以進(jìn)行遞歸剪枝，減少一些重復(fù)計(jì)算，比如說輸入的算式如下：

1 + 1 + 1 + 1 + 1

那么按照算法邏輯，按照運(yùn)算符進(jìn)行分割，一定存在下面兩種分割情況：

(1 + 1) + (1 + 1 + 1)

(1 + 1 + 1) + (1 + 1)

算法會(huì)依次遞歸每一種情況，其實(shí)就是冗余計(jì)算嘛，所以我們可以對(duì)解法代碼稍作修改，加一個(gè)備忘錄來(lái)避免這種重復(fù)計(jì)算：

//備忘錄
HashMap>memo=newHashMap<>();

ListdiffWaysToCompute(Stringinput){
//避免重復(fù)計(jì)算
if(memo.containsKey(input)){
returnmemo.get(input);
}
/******其他都不變******/
Listres=newLinkedList<>();
for(inti=0;i//...
}
if(res.isEmpty()){
res.add(Integer.parseInt(input));
}
/***********************/

//將結(jié)果添加進(jìn)備忘錄
memo.put(input,res);
returnres;
}

當(dāng)然，這個(gè)優(yōu)化沒有改變?cè)嫉膹?fù)雜度，只是對(duì)一些特殊情況做了剪枝，提升了效率。

最后總結(jié)

解決上述算法題利用了分治思想，以每個(gè)運(yùn)算符作為分割點(diǎn)，把復(fù)雜問題分解成小的子問題，遞歸求解子問題，然后再通過子問題的結(jié)果計(jì)算出原問題的結(jié)果。

把大規(guī)模的問題分解成小規(guī)模的問題遞歸求解，應(yīng)該是計(jì)算機(jī)思維的精髓了吧，建議大家多練~