[[429033]]

一、分而治之

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

關于分而治之的實現，都會經歷三個步驟：

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

實際上，關于分而治之的思想，我們在前面已經使用，例如歸并排序的實現，同樣經歷了實現分而治之的三個步驟：

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

同樣關于快速排序的實現，亦如此：

分：選基準，按基準把數組分成兩個字數組

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

合：對兩個字數組進行合并

同樣二分搜索也能使用分而治之的思想去實現，代碼如下：

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) 
    } 
} 

二、動態規劃

動態規劃，同樣是算法設計中的一種方法，是一種在數學、管理科學、計算機科學、經濟學和生物信息學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法

常常適用于有重疊子問題和最優子結構性質的問題

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

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

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

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

適用場景

如果一個問題，可以把所有可能的答案窮舉出來，并且窮舉出來后，發現存在重疊子問題，就可以考慮使用動態規劃

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

關于動態規劃題目解決的步驟，一般如下：

• 描述最優解的結構
• 遞歸定義最優解的值
• 按自底向上的方式計算最優解的值
• 由計算出的結果構造一個最優解

三、區別

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

與分治法不同的是，適合于用動態規劃求解的問題，經分解得到子問題往往「不是互相獨立」的，而分而治之的子問題是相互獨立的

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

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

綜上，可得：

動態規劃：有最優子結構和重疊子問題

分而治之：各子問題獨立

參考文獻

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

https://juejin.cn/post/6951922898638471181