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

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

前言

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

而近兩年隨著互聯網行業競爭愈發激烈，市場上對前端崗位的算法要求也有一定的提升。

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

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

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

本篇博客將分為兩個部分

Part1：通過漫畫形象地講述動態規劃的思想

Part2：配合一道有關動態規劃的LeetCode真題進行實戰演練

Part1：漫畫理解?

? ? ? ? ? ? ?

? ? ? ? ? ?

? ? ? ? ? ? ??

? ? ? ? ?

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

? ? ? ? ? ? ?

? ? ? ? ? ??

? ??

題目：

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

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

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

當然，除此之外，還有很多很多種方式。

? ? ? ? ? ? ??

? ? ? ? ?

? ? ? ? ?

? ? ? ? ? ? ?

? ? ? ? ??

? ? ? ? ?

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

? ? ? ? ? ? ?

? ? ? ? ? ??

? ? ? ? ? ?

? ? ? ? ??

? ? ? ? ??

? ? ? ? ? ??

? ??

第一種:

第二種:

?

? ? ? ? ? ??

? ? ? ? ? ? ?

? ? ? ??

? ? ??

? ? ??

?

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

如圖所示 假設只能通過road1或road2這兩條路徑到達終點

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

到達road1有x條路經(相當于0到8本的放法數量F(8))

到達road2有y條路經(相當于0到9本的放法數量F(9))

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

? ? ? ??

? ? ? ? ? ? ?

? ? ?

??

? ? ? ? ??

? ? ? ? ? ? ? ?

? ? ? ?F(1) = 1;

? ? ? ?F(2) = 2;

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

? ? ? ? ??

? ? ? ? ?

? ? ? ??

? ? ? ? ?

? ? ? ? ??

相信大家看完一定對動態規劃有了一個初步的認識，

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

接下來我們先來通過一道LeetCode實戰原題加深我們對動態規劃的理解

Part2：實戰演練

不同路徑Ⅱ

LeetCode第63題? 原題地址

題目難度 中等

題目描述

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


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

實例1

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

題目解析

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

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

還記得我們之前提到的動態規劃三要素【最優子結構】【邊界】和【狀態轉移公式】嗎？

拿題目中給出的圖片進行舉例：

在不考慮障礙物的情況下，我們利用動態規劃的思想，到達終點有幾種情況呢？

很明顯是兩種:? 從終點上方或終點左方到達

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

那我們很容易得出這個7*3的矩陣的終點 F(7*3) 的最優子結構為 F(6*3) 和 F(7*2）

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

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

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

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

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

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

代碼實現

export default (arr) => {
  let dp = (m, n) => {
    // 檢查起始或者目標元素是不是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)
}

補充：時間復雜度分析

問題分析

感謝同學們在評論區提出的問題

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

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

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

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

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)

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

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

注意到了嗎?

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

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

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

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

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

那么怎樣改進呢?

提出思路

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

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

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

代碼優化

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

參考

程序員小灰—— 漫畫：什么是動態規劃？

今日頭條銀國徽老師——js版數據結構與算法

大家也可以參考FE_Yuan同學針對這篇博客做的補充：前端面試算法-動態規劃

總結

大家發現了嗎，當你掌握了動態規劃的三要素【最優子結構】【邊界】和【狀態轉移公式】

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

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