摘要：我記得大三參加騰訊的校招面試時只準(zhǔn)備了幾種常見的排序算法就足以應(yīng)對了，然而今年包括今日頭條在內(nèi)的多家大廠的前端筆試題目中都出現(xiàn)了貪心算法動態(tài)規(guī)劃分治算法等進(jìn)階性的算法題目。

本篇博客參考今日頭條銀國徽老師的《js版數(shù)據(jù)結(jié)構(gòu)與算法》
Part1改編自《漫畫算法》原作者：程序員小灰

前言

眾所周知，與后臺開發(fā)人員相比，算法是我們前端開發(fā)人員的一個弱項。

而近兩年隨著互聯(lián)網(wǎng)行業(yè)競爭愈發(fā)激烈，市場上對前端崗位的算法要求也有一定的提升。

我記得大三參加騰訊的校招面試時只準(zhǔn)備了幾種常見的排序算法就足以應(yīng)對了，然而今年包括今日頭條在內(nèi)的多家大廠的前端筆試題目中都出現(xiàn)了"貪心算法""動態(tài)規(guī)劃""分治算法"等進(jìn)階性的算法題目。如果在沒有提前準(zhǔn)備的情況下現(xiàn)場應(yīng)對這類進(jìn)階性的算法題目并沒有那么簡單。

如果你這些算法都沒有聽過卻又想進(jìn)大廠的話，別猶豫了，趁著頭發(fā)沒掉光趕緊學(xué)吧！

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

本篇博客將分為兩個部分

Part1：通過漫畫形象地講述動態(tài)規(guī)劃的思想

Part2：配合一道有關(guān)動態(tài)規(guī)劃的LeetCode真題進(jìn)行實(shí)戰(zhàn)演練

Part1：漫畫理解?

? ? ? ? ? ? ?

? ? ? ? ? ?

? ? ? ? ? ? ??

? ? ? ? ?

一一一一一一一一一一一一一一一一一一一一一一一一一

? ? ? ? ? ? ?

? ? ? ? ? ??

? ??

題目：

有一個只能容納10本書的單層書架，你每次只能放1本或2本書。要求用程序求出你將書架填滿一共有多少種方法。

比如，每次放1本書，一共放10次，這是其中一種方法。我們可以簡寫成 1,1,1,1,1,1,1,1,1,1。

再比如，每次放2本書，一共放5次，這是另一種方法。我們可以簡寫成 2,2,2,2,2。

當(dāng)然，除此之外，還有很多很多種方式。

? ? ? ? ? ? ??

? ? ? ? ?

? ? ? ? ?

? ? ? ? ? ? ?

? ? ? ? ??

? ? ? ? ?

一一一一一一一一一一一一一一一一一一一一一一一一一

? ? ? ? ? ? ?

? ? ? ? ? ??

? ? ? ? ? ?

? ? ? ? ??

? ? ? ? ??

? ? ? ? ? ??

? ??

第一種:

第二種:

?

? ? ? ? ? ??

? ? ? ? ? ? ?

? ? ? ??

? ? ??

? ? ??

?

這里為了方便大家理解，我再另外舉一個例子：

如圖所示 假設(shè)只能通過road1或road2這兩條路徑到達(dá)終點(diǎn)

(相當(dāng)于我們把放書的最后一步分為放2本和放1本兩種情況)

到達(dá)road1有x條路經(jīng)(相當(dāng)于0到8本的放法數(shù)量F(8))

到達(dá)road2有y條路經(jīng)(相當(dāng)于0到9本的放法數(shù)量F(9))

那么到達(dá)終點(diǎn)的可能性就是 x+y了 (也就是我們前面推導(dǎo)的 F(10) = F(9)+F(8) )

? ? ? ??

? ? ? ? ? ? ?

? ? ?

??

? ? ? ? ??

? ? ? ? ? ? ? ?

? ? ? ?F(1) = 1;

? ? ? ?F(2) = 2;

? ? ? ?F(n) = F(n-1)+F(n-2)（n>=3）

? ? ? ? ??

? ? ? ? ?

? ? ? ??

? ? ? ? ?

? ? ? ? ??

相信大家看完一定對動態(tài)規(guī)劃有了一個初步的認(rèn)識，

這里大家可以自己先嘗試寫一下這道題的代碼

接下來我們先來通過一道LeetCode實(shí)戰(zhàn)原題加深我們對動態(tài)規(guī)劃的理解

Part2：實(shí)戰(zhàn)演練

不同路徑Ⅱ

LeetCode第63題? 原題地址

題目難度 中等

題目描述

一個機(jī)器人位于一個m x n網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？


 網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。
說明：m和n的值均不超過 100。

實(shí)例1

輸入:
?[?
? ?[0,0,0],?
? ?[0,1,0],
? ?[0,0,0]?
]?
輸出: 2?
解釋:
3x3 網(wǎng)格的正中間有一個障礙物。
?從左上角到右下角一共有 2 條不同的路徑：?
1. 向右 -> 向右 -> 向下 -> 向下?
2. 向下 -> 向下 -> 向右 -> 向右

題目解析

相信大家已經(jīng)看出來了，我們這道題與我們漫畫中演示的題目幾乎一致。

但它又提升了一點(diǎn)難度，我們需要考慮到障礙物的情況。

還記得我們之前提到的動態(tài)規(guī)劃三要素【最優(yōu)子結(jié)構(gòu)】【邊界】和【狀態(tài)轉(zhuǎn)移公式】嗎？

拿題目中給出的圖片進(jìn)行舉例：

在不考慮障礙物的情況下，我們利用動態(tài)規(guī)劃的思想，到達(dá)終點(diǎn)有幾種情況呢？

很明顯是兩種:? 從終點(diǎn)上方或終點(diǎn)左方到達(dá)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 7 * 3 矩陣

那我們很容易得出這個7*3的矩陣的終點(diǎn) F(7*3) 的最優(yōu)子結(jié)構(gòu)為 F(6*3) 和 F(7*2）

至此它的狀態(tài)轉(zhuǎn)移公式也一目了然: F(m*n) = F(m-1*n) + F(m*n-1)

最后我們考慮一下它的邊界情況:

經(jīng)過評論區(qū)同學(xué)的指正，其實(shí)我們之前考慮的F(2*2)邊界情況繼續(xù)往下分也可以分為一列和一行即F(1*2) + F(2*1)兩種情況。

所有的F(m*n)的矩陣最后都可以拆分為一行和一列的情況，所以我們這里邊界情況只有兩種。

第一種邊界F(1*n) 即1行n列

第二種邊界F(n*1) 即n行1列

代碼實(shí)現(xiàn)

export default (arr) => {
  let dp = (m, n) => {
    // 檢查起始或者目標(biāo)元素是不是1(障礙物)，如果起始或者最后那個格就是1，說明怎么都怎么不到那，
    // 直接返回0
    if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
      return 0
    }
    // 有邊界
    if (m < 2 || n < 2) {
      // 第一種邊界 1行n列
      if (m < 2) {
        return arr[m - 1].includes(1) ? 0 : 1
      } else {
        // 第二種邊界 n行1列
        for (let i = 0; i < m; i++) {
          if (arr[i][0] === 1) {
            return 0
          }
        }
        return 1
      }
    } else {
      // 遞歸
      return dp(m - 1, n) + dp(m, n - 1)
    }
  }
  return dp(arr.length, arr[0].length)
}

補(bǔ)充：時間復(fù)雜度分析

問題分析

感謝同學(xué)們在評論區(qū)提出的問題

首先說明我們上方代碼是沒有問題的，但是在LeetCode上的第27個測試用例上超出了時間限制

這個測試用例相對復(fù)雜，是一個33*22的二維矩陣

那為什么矩陣到達(dá)一定長度時我們的方法時間復(fù)雜度會過高呢?

我們先回顧一下我們之前的思路:

F(10) = F(9) + F(8)? ? ? ? ? ? ?

F(9) = F(8) + F(7)? ? ??

將F(9)分解后那么F(10) 可以寫成

?F(8) + F(8) + F(7)

而F(8) 又= F(7) + F(6)

那么繼續(xù)將F(8)分解 F(10) 可以寫成?

F(7) + F(7) +F(7) + F(6) + F(6)

注意到了嗎?

越向下劃分重復(fù)的就越多，可能你會覺得不就是多加一次F(n)的值嗎

但是這里我必須要提醒你的是：

F(n)不單純是一個值的引用，他是一個遞歸函數(shù)，我們每重復(fù)一次它都會重新執(zhí)行一次F函數(shù)

我們不討論時間復(fù)雜度具體怎樣計算

但這里我可以告訴大家我們之前的方法時間復(fù)雜度是O(2^n)

那么怎樣改進(jìn)呢?

提出思路

在這里提出兩個思路，大家也可以嘗試自己寫一下：

緩存每一次計算出的值，也就是記錄下F(9),F(8),F(7)...的值，每次遞歸到有之前計算過數(shù)據(jù)直接拿值，而不用再次重復(fù)調(diào)用遞歸函數(shù)。

從下向上(由起點(diǎn)至終點(diǎn))計算，由于每次只依賴前兩個數(shù)據(jù)，通過兩個變量只保存前兩次的數(shù)據(jù)就可以了，如計算F(3)只依賴F(1)和F(2)，計算F(6)只依賴F(5)和F(4)。

代碼優(yōu)化

// 傳入二維數(shù)組
arr => {
    // 行數(shù)
    let n = arr.length;
    if(!n){
        return 0;
    }
    // 列數(shù)
    let m = arr[0].length;
    // 起點(diǎn)或終點(diǎn)為障礙物
    if(arr[0][0] === 1 || arr[n - 1][m - 1] === 1){
        return 0;
    }
    // 記錄到達(dá)每個位置的路徑可能數(shù)
    var rode= [];
    // 遍歷每一行
    for(let i = 0; i < n; i++){
        rode[i] = [];    // 遍歷每一行的每個元素
        for(let j = 0; j < m; j++){
            // 若某節(jié)點(diǎn)是障礙物，則通向該節(jié)點(diǎn)的路徑數(shù)量為0
            if(arr[i][j] === 1){
                rode[i][j] = 0;
            } else if(i === 0){
                // 若是第一行 每個節(jié)點(diǎn)是否能通過都依賴它左方節(jié)點(diǎn)
                rode[i][j] = rode[i][j - 1] === 0 ? 0 : 1;
            } else if(j === 0){
                // 若是第一列 每個節(jié)點(diǎn)是否能通過都依賴它上方節(jié)點(diǎn)                
                rode[i][j] = rode[i - 1][j] === 0 ? 0 : 1;
            } else {
                // 否則遞歸
                rode[i][j] = rode[i - 1][j] + rode[i][j - 1];
            }
        }
    }
    return rode[n - 1][m - 1];
}

參考

程序員小灰—— 漫畫：什么是動態(tài)規(guī)劃？

今日頭條銀國徽老師——js版數(shù)據(jù)結(jié)構(gòu)與算法

大家也可以參考FE_Yuan同學(xué)針對這篇博客做的補(bǔ)充：前端面試算法-動態(tài)規(guī)劃

總結(jié)

大家發(fā)現(xiàn)了嗎，當(dāng)你掌握了動態(tài)規(guī)劃的三要素【最優(yōu)子結(jié)構(gòu)】【邊界】和【狀態(tài)轉(zhuǎn)移公式】

后，解決動態(tài)規(guī)劃的算法題目并不是很難。但是其中的思想是需要我們好好消化吸收的。

相信以后遇到這類問題你也可以迎刃而解。