[[429033]]

一、分而治之

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

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

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

實際上，關(guān)于分而治之的思想，我們在前面已經(jīng)使用，例如歸并排序的實現(xiàn)，同樣經(jīng)歷了實現(xiàn)分而治之的三個步驟：

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

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

分：選基準，按基準把數(shù)組分成兩個字數(shù)組

解：遞歸地對兩個字數(shù)組進行快速排序

合：對兩個字數(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) 
    } 
} 

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

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

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

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

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

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

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

適用場景

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

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

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

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

三、區(qū)別

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

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

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

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

綜上，可得：

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

分而治之：各子問題獨立

參考文獻

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

https://juejin.cn/post/6951922898638471181