好看的历史书籍推荐,小说,欢乐颂小说

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

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

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

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

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

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

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

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

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 題講講什么是分治算法，先看看題目：

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

函數(shù)簽名如下：

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

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

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

廢話不多說，解決本題的關鍵有兩點：

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

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

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

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

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

下面來具體解釋下這兩個關鍵點怎么理解。

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

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ī)律了么？其實就是按照運算符進行分割，給每個運算符的左右兩部分加括號，這就是之前說的第一個關鍵點，不要考慮整體，而是聚焦每個運算符。

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

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

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

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

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

(1) + (2 * 3) = 7

(1 + 2) * (3) = 9

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

1 + 2 * 3 = [9, 7]

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

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

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

9 - 20 = -11

7 - 20 = -13

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

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

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

這個函數(shù)不就是干這個事兒的嗎？這就是我們之前說的第二個關鍵點，明確函數(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)這個例子是如何計算的，你應該完全理解了吧，那么回來看我們的原始問題。

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

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

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

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

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

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

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

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));
/******治******/
//通過子問題的結果，合成原問題的結果
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;
}

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

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

當然，一個重點在這段代碼：

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

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

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

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

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

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

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

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

1 + 1 + 1 + 1 + 1

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

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

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

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

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

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

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