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

其實，我覺得回溯、分治和動態(tài)規(guī)劃算法可以劃為一類，因為它們都會涉及遞歸。

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

動態(tài)規(guī)劃是一類算法問題，肯定是讓你求最值的。因為動態(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)造出原問題的答案。這里有點類似動態(tài)規(guī)劃，所以說運用分治算法也需要滿足一些條件，你的原問題結(jié)果應(yīng)該可以通過合并子問題結(jié)果來計算。

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

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

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

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

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

下面來看一道具體的算法題。

添加括號的所有方式

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

簡單說，就是給你輸入一個算式，你可以給它隨意加括號，請你窮舉出所有可能的加括號方式，并計算出對應(yīng)的結(jié)果。

函數(shù)簽名如下：

//計算所有加括號的結(jié)果
ListdiffWaysToCompute(Stringinput);

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

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

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

1、不要思考整體，而是把目光聚焦局部，只看一個運算符。

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

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

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

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

下面來具體解釋下這兩個關(guān)鍵點怎么理解。

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

1 + 2 * 3 - 4 * 5

請問，這個算式有幾種加括號的方式？請在一秒之內(nèi)回答我。

估計你回答不出來，因為括號可以嵌套，要窮舉出來肯定得費點功夫。

不過呢，嵌套這個事情吧，我們?nèi)祟悂砜词呛茴^疼的，但對于算法來說嵌套括號不要太簡單，一次遞歸就可以嵌套一層，一次搞不定大不了多遞歸幾次。

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

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

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

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

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

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

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

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

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

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

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

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

(1) + (2 * 3) = 7

(1 + 2) * (3) = 9

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

1 + 2 * 3 = [9, 7]

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

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

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

9 - 20 = -11

7 - 20 = -13

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

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

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

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

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

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

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)這個例子是如何計算的，你應(yīng)該完全理解了吧，那么回來看我們的原始問題。

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

不是，每個運算符都可以把原問題分割成兩個子問題，剛才已經(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中的運算符
if(c=='-'||c=='*'||c=='+'){
/******分******/
//以運算符為中心，分割成兩個字符串，分別遞歸計算
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為空，說明算式是一個數(shù)字，沒有運算符
if(res.isEmpty()){
res.add(Integer.parseInt(input));
}
returnres;
}

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

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

當(dāng)然，一個重點在這段代碼：

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

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

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

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

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

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

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

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

1 + 1 + 1 + 1 + 1

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

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

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

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

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

ListdiffWaysToCompute(Stringinput){
//避免重復(fù)計算
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)然，這個優(yōu)化沒有改變原始的復(fù)雜度，只是對一些特殊情況做了剪枝，提升了效率。

最后總結(jié)

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

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