[[429033]]

一、分而治之

分而治之是算法設(shè)計(jì)中的一種方法，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并

關(guān)于分而治之的實(shí)現(xiàn)，都會(huì)經(jīng)歷三個(gè)步驟：

• 分解：將原問題分解為若干個(gè)規(guī)模較小，相對(duì)獨(dú)立，與原問題形式相同的子問題
• 解決：若子問題規(guī)模較小且易于解決時(shí)，則直接解。否則，遞歸地解決各子問題
• 合并：將各子問題的解合并為原問題的解

實(shí)際上，關(guān)于分而治之的思想，我們?cè)谇懊嬉呀?jīng)使用，例如歸并排序的實(shí)現(xiàn)，同樣經(jīng)歷了實(shí)現(xiàn)分而治之的三個(gè)步驟：

• 分解：把數(shù)組從中間一分為二
• 解決：遞歸地對(duì)兩個(gè)子數(shù)組進(jìn)行歸并排序
• 合并：將兩個(gè)字?jǐn)?shù)組合并稱有序數(shù)組

同樣關(guān)于快速排序的實(shí)現(xiàn)，亦如此：

分：選基準(zhǔn)，按基準(zhǔn)把數(shù)組分成兩個(gè)字?jǐn)?shù)組

解：遞歸地對(duì)兩個(gè)字?jǐn)?shù)組進(jìn)行快速排序

合：對(duì)兩個(gè)字?jǐn)?shù)組進(jìn)行合并

同樣二分搜索也能使用分而治之的思想去實(shí)現(xiàn)，代碼如下：

function binarySearch(arr,l,r,target){ 
    if(l> r){ 
        return -1; 
    } 
    let mid = l + Math.floor((r-l)/2) 
    if(arr[mid] === target){ 
        return mid; 
    }else if(arr[mid] < target ){ 
        return binarySearch(arr,mid + 1,r,target) 
    }else{ 
        return binarySearch(arr,l,mid - 1,target) 
    } 
} 

二、動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃，同樣是算法設(shè)計(jì)中的一種方法，是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過把原問題分解為相對(duì)簡(jiǎn)單的子問題的方式求解復(fù)雜問題的方法

常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題

簡(jiǎn)單來說，動(dòng)態(tài)規(guī)劃其實(shí)就是，給定一個(gè)問題，我們把它拆成一個(gè)個(gè)子問題，直到子問題可以直接解決

然后呢，把子問題答案保存起來，以減少重復(fù)計(jì)算。再根據(jù)子問題答案反推，得出原問題解的一種方法。

一般這些子問題很相似，可以通過函數(shù)關(guān)系式遞推出來，例如斐波那契數(shù)列，我們可以得到公式：當(dāng) n 大于 2的時(shí)候，F(xiàn)(n) = F(n-1) + F(n-2) ，

f(10)= f(9)+f(8),f(9) = f(8) + f(7)...是重疊子問題，當(dāng)n = 1、2的時(shí)候，對(duì)應(yīng)的值為2，這時(shí)候就通過可以使用一個(gè)數(shù)組記錄每一步計(jì)算的結(jié)果，以此類推，減少不必要的重復(fù)計(jì)算

適用場(chǎng)景

如果一個(gè)問題，可以把所有可能的答案窮舉出來，并且窮舉出來后，發(fā)現(xiàn)存在重疊子問題，就可以考慮使用動(dòng)態(tài)規(guī)劃

比如一些求最值的場(chǎng)景，如最長(zhǎng)遞增子序列、最小編輯距離、背包問題、湊零錢問題等等，都是動(dòng)態(tài)規(guī)劃的經(jīng)典應(yīng)用場(chǎng)景

關(guān)于動(dòng)態(tài)規(guī)劃題目解決的步驟，一般如下：

• 描述最優(yōu)解的結(jié)構(gòu)
• 遞歸定義最優(yōu)解的值
• 按自底向上的方式計(jì)算最優(yōu)解的值
• 由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解

三、區(qū)別

動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解

與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往「不是互相獨(dú)立」的，而分而治之的子問題是相互獨(dú)立的

若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次

如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間

綜上，可得：

動(dòng)態(tài)規(guī)劃：有最優(yōu)子結(jié)構(gòu)和重疊子問題

分而治之：各子問題獨(dú)立

參考文獻(xiàn)

https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408

https://juejin.cn/post/6951922898638471181