日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
面試官：說(shuō)說(shuō)你對(duì)分而治之、動(dòng)態(tài)規(guī)劃的理解？區(qū)別？

一、分而治之

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

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

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

實(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)，代碼如下：

 
 
 
 
    
  
  
  
  
  1. function binarySearch(arr,l,r,target){
    2. 
  
  
  
  
  2.     if(l> r){
    3. 
  
  
  
  
  3.         return -1;
    4. 
  
  
  
  
  4.     }
    5. 
  
  
  
  
  5.     let mid = l + Math.floor((r-l)/2)
    6. 
  
  
  
  
  6.     if(arr[mid] === target){
    7. 
  
  
  
  
  7.         return mid;
    8. 
  
  
  
  
  8.     }else if(arr[mid] < target ){
    9. 
  
  
  
  
  9.         return binarySearch(arr,mid + 1,r,target)
    10. 
  
  
  
  
  10.     }else{
    11. 
  
  
  
  
  11.         return binarySearch(arr,l,mid - 1,target)
    12. 
  
  
  
  
  12.     }
    13. 
  
  
  
  
  13. }
    14.

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

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

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

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

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

一般這些子問(wèn)題很相似，可以通過(guò)函數(shù)關(guān)系式遞推出來(lái)，例如斐波那契數(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)...是重疊子問(wèn)題，當(dāng)n = 1、2的時(shí)候，對(duì)應(yīng)的值為2，這時(shí)候就通過(guò)可以使用一個(gè)數(shù)組記錄每一步計(jì)算的結(jié)果，以此類推，減少不必要的重復(fù)計(jì)算

適用場(chǎng)景

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

比如一些求最值的場(chǎng)景，如最長(zhǎng)遞增子序列、最小編輯距離、背包問(wèn)題、湊零錢問(wèn)題等等，都是動(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ī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解

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

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

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

綜上，可得：

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

分而治之：各子問(wèn)題獨(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


當(dāng)前名稱：面試官：說(shuō)說(shuō)你對(duì)分而治之、動(dòng)態(tài)規(guī)劃的理解？區(qū)別？
分享路徑：http://www.dlmjj.cn/article/dpgcojo.html