21 道 LeetCode 題解帶你搞懂動態規劃！

動態規劃是前端面試中常考的一種算法，下面就來看看動態規劃的概念和使用場景，以及 LeetCode 中常考的動態規劃題目該如何解答！

一、動態規劃概述

1. 基本概念

動態規劃算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，而我們希望找到具有最優值的解。動態規劃算法與分治法類似，基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。

動態規劃問題經分解得到的子問題往往不是互相獨立的。需要保存已解決的子問題的答案，而在需要時再找出已保存的答案，這樣就可以避免大量的重複計算。可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。

動態規劃有兩個重要的概念：

• 狀態：解決某一問題的中間結果，它是子問題的一個抽象定義。

• 狀態轉移方程：狀態與狀態之間的遞推關係。

動態規劃解題步驟：

1. 狀態定義：找出子問題抽象定義。

2. 確定狀態轉移方程：找出狀態與狀態之間的遞推關係。

3. 初始狀態和邊界情況：最簡單的子問題的結果，也是程序的出口條件 。

4. 返回值：對於簡單問題，返回值可能就是最終狀態；對於複雜問題可能還需對最終狀態做一些額外處理。

下面就通過爬樓梯問題來看看動態規劃的具體應用。

題目描述：假設正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？其中 n 是一個正整數。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

這道題有兩個關鍵特徵：

• 要求給出達成某個目的的解法個數；

• 不要求給出每一種解法對應的具體路徑。

這樣的問題往往可以用動態規劃進行求解。對於這個問題，每次爬樓梯只有兩種情況：

• 最後一步爬 1 級臺階，前面有 n - 1 級臺階，這種情況下共有 f(n - 1) 種方法；

• 最後一步爬 2 級臺階，前面有 n - 2 級臺階，這種情況下共有 f(n - 2) 種方法；

f(n) 爲以上兩種情況之和，即 f(n)=f(n-1)+f(n-2)，這就是本題用到的遞推關係。下面就根據動態規劃的四個步驟來看一下：

1. 狀態定義：初始化一個 f 數組，f[i] 表示爬到 i 級臺階的方法數量；

2. 狀態轉移方程：f(n)=f(n-1)+f(n-2)；

3. 初始狀態：一級臺階時，共 1 種爬法；兩級臺階時，可以一級一級爬，也可以一次爬兩級，共有 2 種爬法。即 f[1] = 1，f[2] = 2；

4. 返回值：f[n] ，即 n 級臺階共有多少種爬法。

動態規劃實現代碼如下：

/**
* @param {number} n
* @return {number}
*/
const climbStairs = function(n) {
    // 初始化狀態數組
    const f = [];
    // 初始化已知值
    f[1] = 1;
    f[2] = 2;
    // 動態更新每一層樓梯對應的結果
    for(let i = 3;i <= n;i++){
        f[i] = f[i-2] + f[i-1];
    }
    // 返回目標值
    return f[n];
};

2. 使用場景

上面用動態規劃的思想解決了 “爬樓梯” 的問題，當然我們的目的並不是爲了解決這個問題，而是通過這個問題來看動態規劃，下面就來重新認識一下動態規劃。

上面說過分支問題，它的核心思想是：把一個問題分解爲相互獨立的子問題，逐個解決子問題後，再組合子問題的答案，就得到了問題的最終解。

動態規劃的思想和 “分治” 有點相似。不同之處在於，“分治”思想中，各個子問題之間是獨立的：比如說歸併排序中，子數組之間的排序並不互相影響。而動態規劃劃分出的子問題，往往是相互依賴、相互影響的。

那什麼樣的題應該用動態規劃來做？要抓以下關鍵特徵：

• 最優子結構，它指的是問題的最優解包含着子問題的最優解——不管前面的決策如何，此後的狀態必須是基於當前狀態（由上次決策產生）的最優決策。就這道題來說，f(n)和f(n-1)、f(n-2)之間的關係（狀態轉移方程）印證了這一點。

• 重疊子問題，在遞歸的過程中，出現了反覆計算的情況。

• 無後效性，無後效性有兩層含義，第一層含義是，在推導後面階段的狀態的時候，只關心前面階段的狀態值，不關心這個狀態是怎麼一步一步推導出來的。第二層含義是，某階段狀態一旦確定，就不受之後階段的決策影響。無後效性是一個非常 “寬鬆” 的要求。只要滿足前面提到的動態規劃問題模型，其實基本上都會滿足無後效性。

所以，只要需要解決的問題符合這三個關鍵特徵，就可以使用動態規劃來求解。

二、LeetCode 路徑問題

1. 不同路徑

一個機器人位於一個 m x n網格的左上角 （起始點在下圖中標記爲 “Start” ）。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記爲 “Finish” ）。

問總共有多少條不同的路徑？示例 1：

輸入：m = 3, n = 7
輸出：28

示例 2：

輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

輸入：m = 7, n = 3
輸出：28

示例 4：

輸入：m = 3, n = 3
輸出：6

提示：

• 1 <= m, n <= 100

• 題目數據保證答案小於等於 2 * 10

這個題目和爬樓梯問題其實是一樣的思路，只不過爬樓梯問題算是一維的問題，而這個問題是一個二維的問題。看到這個問題，我們自然而然得就能想到動態規劃。

每一個網格的路徑數都和其上側和左側的路徑數相關，可以得出遞推方程：

a[i][j] = a[i - 1][j] + a[i][j - 1]

首先初始化一個 m * n 的二維數組，數組的所有節點值都先初始爲 0，由於最上邊一行和最左邊一列都是邊界，只能有一種走法，所以初始爲 1。然後根據遞推方程求解即可。

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))

    for(let i = 0; i < m; i++){
        dp[i][0] = 1
    }
    for(let j = 0; j < n; j++){
        dp[0][j] = 1
    }

    for(let i = 1; i < m; i++){ 
        for(let j = 1; j < n; j++){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};

複雜度分析：

• 時間複雜度：O(mn)，其中 m 和 n 分別是網格的長寬，我們需要兩層遍歷，所以空間複雜度爲 O(mn)。

• 空間複雜度：O(mn)，其中 m 和 n 分別是網格的長寬，我們需要一個 m * n 的二維數組來存儲所有狀態，所以所需空間複雜度爲 O(mn)。

2. 不同路徑 II

一個機器人位於一個 m x n 網格的左上角 （起始點在下圖中標記爲 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記爲 “Finish”）。

現在考慮網格中有障礙物。那麼從左上角到右下角將會有多少條不同的路徑？

網格中的障礙物和空位置分別用 1 和 0 來表示。

示例 1：

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

示例 2：

輸入：obstacleGrid = [[0,1],[0,0]]
輸出：1

提示：

• m == obstacleGrid.length

• n == obstacleGrid[i].length

• 1 <= m, n <= 100

• obstacleGrid[i][j] 爲 0 或 1

這道題目和 62 題不同路徑 是一樣的思路：動態規劃。

不同的是，這個題目中出現了障礙物，所以在遍歷的時候需要注意以下兩點：

• 在給第一行和第一列元素設置初始值時，如果遇到網格的值是 1，也就是有障礙物的情況，就直接停下來，不需要往前繼續遍歷了，因爲前面就不可能在經過了；

• 在計算每個網格的路徑數時，如果該方格元素是就直接跳過，不需要計算。

以上兩點就是本題和 62 題的不同之處，根據這個思路實現即可。

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    if(!obstacleGrid.length || obstacleGrid[0][0] === 1){
        return 0
    }

    const m = obstacleGrid.length, n = obstacleGrid[0].length
    const dp = new Array(m).fill(0).map(() =>  new Array(n).fill(0))

    for (let i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
        dp[0][j] = 1;
    }
    
    for(let i = 1; i < m; i++){ 
        for(let j = 1; j < n; j++){
            if(obstacleGrid[i][j] === 0){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
    }
    return dp[m - 1][n - 1]
};

複雜度分析：

• 時間複雜度：O(mn)，其中 m 和 n 分別是網格的長寬，我們需要兩層遍歷，所以空間複雜度爲 O(mn)。

• 空間複雜度：O(mn)，其中 m 和 n 分別是網格的長寬，我們需要一個 m * n 的二維數組來存儲所有狀態，所以所需空間複雜度爲 O(mn)。

3. 最小路徑和

給定一個包含非負整數的 _m_ x _n_ 網格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和爲最小。** 說明：** 每次只能向下或者向右移動一步。 

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因爲路徑 1→3→1→1→1 的總和最小。

示例 2：

輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 200

• 0 <= grid[i][j] <= 100

對於這道題目，路徑的方向只能是從上到下，從左向右。我們可以知道，當前點的路徑和都和上一個點的路徑和相關，所以這裏我們可以使用動態規劃來解答。

對於第一行的元素，它只能是左邊的元素移動過來的，當前的元素的路徑總和關係如下：

grid[i][0] += grid[i - 1][0]

對於第一列的元素，它只能是上邊的元素移動過來的，當前的元素的路徑總和關係如下：

grid[0][j] += grid[0][j - 1]

對於其他位置的元素，他可以是上邊移動過來的，也可以是左邊移動過來的，因爲要求的是最小路徑和，所以我們只需要選取左邊和上面的路徑和最小值，當前的元素的路徑總和關係如下：

grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];

這樣，經過遍歷之後，每個節點的值就是當前的最小路徑和。最後只需要返回右下角元素的值即可。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let m = grid.length, n = grid[0].length

    for(let i = 1; i < m; i++){
        grid[i][0] += grid[i - 1][0]
    }
    for(let j = 1; j < n; j++){
        grid[0][j] += grid[0][j - 1]
    }

    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
        }
    }
    return grid[m - 1][n - 1]
}

複雜度分析：

• 時間複雜度：O(mn)，其中 m 和 n 分別是網格的行數和列數。需要對整個網格遍歷一次，計算 grid 的每個元素的值。

• 空間複雜度：O(1)，這裏我們是在原數組的基礎上進行的操作，所需的額外的空間爲常數。

4. 三角形最小路徑和

給定一個三角形 triangle ，找出自頂向下的最小路徑和。

每一步只能移動到下一行中相鄰的結點上。** 相鄰的結點 ** 在這裏指的是 **下標** 與 **上一層結點下標** 相同或者等於 **上一層結點下標 + 1** 的兩個結點。也就是說，如果正位於當前行的下標 i ，那麼下一步可以移動到下一行的下標 i 或 i + 1 。 **示例 1：**

輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出：11
解釋：如下面簡圖所示：
   2
  3 4
 6 5 7
4 1 8 3
自頂向下的最小路徑和爲 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

輸入：triangle = [[-10]]
輸出：-10

提示：

• 1 <= triangle.length <= 200

• triangle[0].length == 1

• triangle[i].length == triangle[i - 1].length + 1

• -104 <= triangle[i][j] <= 104

進階：

• 你可以只使用 O(n) 的額外空間（n 爲三角形的總行數）來解決這個問題嗎？

這道題目和最小路徑和那道題的階梯思路類似，都是使用動態規劃來解決。

這裏，其實我們並不需要初始化一個數組來保存每一步的狀態（每個節點的最小路徑值），可以在原數組上進行操作，因爲每個節點都只遍歷一次，在遍歷完之後，我們只需要將當前節點的狀態賦值給當前節點即可。

這裏同樣需要處理兩個邊界的問題，對於第一列元素，他只能是上面的元素下來的，所以他的狀態轉移方程是：

triangle[i][j] += triangle[i - 1][j]

對於每一行的最後一位，它只能是上一行的最後一位下來的，所以他的狀態轉移方程是：

triangle[i][j] += triangle[i - 1][j - 1]

對於其他的元素，可以是其對應序號以及對應序號減一的元素移動下來的，所以他的狀態轉移方程是：

triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])

最後我們只需要返回最後一行元素的最小值即可，這裏我們用... 擴展運算符配合 Math 的 min 方法求得最後一行的最小值。

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    const n = triangle.length

    for(let i = 1; i < n; i++){
        for(let j = 0; j <= i; j++){
            if(j === 0){
                triangle[i][j] += triangle[i - 1][j]
            }else if(j === i){
                triangle[i][j] += triangle[i - 1][j - 1]
            }else{
                triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])
            }
        }
    }

    return Math.min(...triangle[n - 1])
};

複雜度分析：

• 時間複雜度：O(n2)，其中 n 是三角形的行數。

• 空間複雜度：O(1)。這裏我們在原數組的基礎上進行的操作，所以所需要的額外的空間爲常數。

三、LeetCode 買賣股票問題

1. 買賣股票的最佳時機

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。如果你最多隻允許完成一筆交易（即買入和賣出一支股票一次），設計一個算法來計算你所能獲取的最大利潤。注意：你不能在買入股票前賣出股票。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因爲賣出價格需要大於買入價格；同時，你不能在買入前賣出股票。

示例 2:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤爲 0。

（1）直接遍歷我們需要對股票進行一次買入、一次賣出，賣出在買入之後，並且要計算最大的利潤。

這裏初始化一個最小值 min，和一個最大的結果值 max。遍歷數組，如果當前數組元素小於最小值民，就更新最小值，始終讓其保持最小。如果當前值減去最小值大於最大值，就更新最大值。直到遍歷完數組所有的元素，返回最後的結果。

（2）動態規劃對於這道題，我們可以使用動態規劃來解決。這裏我們只需要進行一次買入賣出。那到最後交易時，可能會有三種狀態：

• dp[0]：一直沒有買

• dp[1]：：到最後只買了一筆，未賣出

• dp[2]：：到最後只賣了一筆，並賣出

由於第一種狀態未進行任何操作，所以可以不用記錄。然後我們對後兩種狀態進行轉移：

• dp[1] = Math.max(dp[1], -prices[i])：前一天也是 b1 狀態或者是沒有任何操作，今天買入一筆變成 b1 狀態；

• dp[2] = Math.max(dp[2], dp[1] + prices[i])：前一天也是 s1 狀態或者是 b1 狀態，今天賣出一筆變成 s1 狀態；

（1）直接遍歷

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let max = 0
    let min = prices[0]

    prices.forEach( item => {
        if(item < min) min = item
        if(item - min > max) max = item - min
    })
    return max
};

複雜度分析：

• 時間複雜度： O(n)，其中 n 是數組的長度，我們需要將數組遍歷一遍

• 空間複雜度： O(1)，這裏只需要常數空間來儲存最小值 min 和最大結果值 max

（2）動態規劃

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let len = prices.length;
    const dp = [0, -prices[0], 0]
    
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], -prices[i])
        dp[2] = Math.max(dp[2], dp[1] + prices[i])
    }
    return dp[2];
}

複雜度分析：

• 時間複雜度：O(n)，其中 n 是數組 prices 的長度。

• 空間複雜度：O(1)。

2. 買賣股票的最佳時機 II

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。設計一個算法來計算你所能獲取的最大利潤。你可以儘可能地完成更多的交易（多次買賣一支股票）。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

示例 2:

輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。
     因爲這樣屬於同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤爲 0。

提示：

• 1 <= prices.length <= 3 * 10

• 0 <= prices[i] <= 10

對於這道題目，我們可以使用動態規劃來解答。每個點的狀態描述：手裏有股票或者沒股票。

1）dp[i][0] 表示：第 i 天手裏沒股票，至今（第 i 天）的最大收益。第 i 天手裏沒股票，有兩種可能：

• 昨天也沒持有股票：dp[i-1][0]

• 昨天買了股票，今天賣了: dp[i-1][1] + prices[i]

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

2）dp[i][1] 表示：第 i 天手裏有股票，至今（第 i 天）的最大收益。第 i 天手裏有股票，有兩種可能：

• 昨天也有股票：dp[i-1][1]

• 昨天賣了，今天買了: dp[i-1][0] - prices[i]

• dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

最終目標是求出：dp[prices.length-1][0]和dp[prices.length-1][1]的較大者，前者肯定 >= 後者，求dp[prices.length-1][0]即可。

對於開始：

• day 0 沒買: dp[0][0] = 0

• day 0 買了: dp[0][1] = -prices[0]

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  const len = prices.length;
  if (len < 2) {
    return 0;
  };
  const dp = new Array(len);
  dp[0] = [0, -prices[0]];
  for (let i = 1; i < len; i++) {
    dp[i] = new Array(2);
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 沒有股票
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 有股票
  }
  return dp[len - 1][0];
}

複雜度分析：

• 時間複雜度： O(n)，其中 n 爲數組的長度。一共有 2n 個狀態，每次狀態轉移的時間複雜度爲 O(1)，因此時間複雜度爲 O(2n)=O(n)。

• 空間複雜度：O(n)，我們需要開闢 O(n) 空間存儲動態規劃中的所有狀態。

3. 買賣股票的最佳時機 III

給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。
     隨後，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。

示例 2：

輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。   
     因爲這樣屬於同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3：

輸入：prices = [7,6,4,3,1] 
輸出：0 
解釋：在這個情況下, 沒有交易完成, 所以最大利潤爲 0。

示例 4：

輸入：prices = [1]
輸出：0

提示：

• 1 <= prices.length <= 105

• 0 <= prices[i] <= 105

對於這道題，我們可以使用動態規劃來解決。在《買賣股票的最佳時機》中，我們只能進行一次買入賣出。而這道題，我們可以進行至多兩次的買入賣出，那到最後交易時，可能會有五種狀態：

• dp[0]：一直沒有買

• dp[1]：到最後只買了一筆，未賣出

• dp[2]：到最後只賣了一筆，並賣出

• dp[3]：到最後買了兩筆，只賣出一筆

• dp[4]：到最後買了兩筆，兩筆都賣出

由於第一種狀態未進行任何操作，所以可以不用記錄。然後我們對後四種狀態進行轉移：

• dp[1] = Math.max(dp[1], -prices[i])：前一天也是 b1 狀態或者是沒有任何操作，今天買入一筆變成 b1 狀態；

• dp[2] = Math.max(dp[2], dp[1] + prices[i])：前一天也是 s1 狀態或者是 b1 狀態，今天賣出一筆變成 s1 狀態；

• dp[3] = Math.max(dp[3], dp[2] - prices[i])：前一天也是 b2 狀態或者是 s1 狀態，今天買入一筆變成 b2 狀態；

• dp[4] = Math.max(dp[4], dp[3] + prices[i])：前一天也是 s2 狀態或者是 b2 狀態，今天冒出一筆變成 s2 狀態。

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
    let len = prices.length;
    const dp = [0, -prices[0], -prices[0], 0, 0]
    
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], -prices[i])
        dp[2] = Math.max(dp[2], dp[1] + prices[i])
        dp[3] = Math.max(dp[3], dp[2] - prices[i])
        dp[4] = Math.max(dp[4], dp[3] + prices[i])
    }
    return dp[4];
};

複雜度分析：

• 時間複雜度：O(n)，其中 n 是數組 prices 的長度。

• 空間複雜度：O(1)。

4. 買賣股票的最佳時機 IV

給定一個整數數組 prices ，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1：

輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。

示例 2：

輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。
     隨後，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。

提示：

• 0 <= k <= 100

• 0 <= prices.length <= 1000

• 0 <= prices[i] <= 1000

在題目《買賣股票的最佳時機》中，我們只能進行一次買入賣出，在題目 123《買賣股票的最佳時機 III》中，我們可以進行兩次買入賣出操作。而在這道題目中，我們可以進行 k 次買入賣出操作。這裏我們也可以使用動態規劃來解答。

每次我們只能進行[1, k]次中的某次交易或不交易，所以可能有 2k+1 中狀態：

• 無操作，一直沒有買

• dp[0]：到最後只買了一筆，未賣出

• dp[1]：到最後只賣了一筆，並賣出

• dp[2]：到最後買了兩筆，只賣出一筆

• dp[3]：到最後買了兩筆，兩筆都賣出

• dp[4]：到最後買了三筆，只賣出兩筆

• ······

我們可以枚舉一天的所有可能，取現金最大值：

• 不交易，現金 不變

• 進行[1, k]的某次交易

• 買入，現金 -= 當天股票價格

• 賣出，現金 += 當天股票價格

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    const dp = new Int16Array(k * 2).fill(-prices[0])
    
    for (let i = 0; i < prices.length; i++) {
        for (let j = 0; j < dp.length; j++) 
            {
                dp[j] = Math.max(dp[j], (dp[j - 1] || 0) + (j & 1 ? prices[i] : -prices[i]))
            }
    }
    return Math.max(0, ...dp) 
};

複雜度分析：

• 時間複雜度：O(n * min(n, k))，其中 n 是數組 prices 的長度，即使用雙重循環進行動態規劃需要的時間。

• 空間複雜度：O(min(n,k))。

四、LeetCode 打家劫舍問題

1. 打家劫舍

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 ** 不觸動警報裝置的情況下 **，一夜之內能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然後偷竊 3 號房屋 (金額 = 3)。
     偷竊到的最高金額 = 1 + 3 = 4 。

示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接着偷竊 5 號房屋 (金額 = 1)。
     偷竊到的最高金額 = 2 + 9 + 1 = 12 。

提示：

• 0 <= nums.length <= 100

• 0 <= nums[i] <= 400

對於這道題目，我們可以使用動態規劃來實現。首先來看最簡單的兩種情況，如果只有一間房屋，那這個屋子就是最高的金額，如果有兩間房屋，那不能同時偷，只能偷其中其中金額高的那間，如果大於兩間屋子，就要進行討論了。

• 如果偷第 n 個房間，那麼就不能偷第 n - 1 個房間，那麼總金額就是前 n - 2 間屋子能偷到的最高的金額之和；

• 如果不偷第 k 間屋，那麼能偷到的總金額就是前 k - 1 個房間的最高總金額。

這兩者，我們只要取總金額的較大值即可。

我們可以用 dp[i] 表示前 i 間房屋能偷竊到的最高總金額，那麼就有如下的狀態轉移方程：

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

邊界條件爲：

• dp[0] = nums[0] ：只有一間房屋，則偷竊該房屋

• dp[1] = max(nums[0], nums[1])：只有兩間房屋，選擇其中金額較高的房屋進行偷竊

最終的答案即爲 dp[n−1]，其中 n 是數組的長度。

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length
    if(!len){
        return 0
    }

    const dp = new Array(len + 1)
    dp[0] = 0
    dp[1] = nums[0]

    for(let i = 2; i <= len; i++){
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
    }
    return dp[len];
};

複雜度分析：

• 時間複雜度：O(n)，其中 n 是數組長度。只需要對數組遍歷一次。

• 空間複雜度：O(1)。使用數組只存儲前兩間房屋的最高總金額，而不需要存儲整個數組的結果，因此空間複雜度是 O(1)

2. 打家劫舍 II

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味着第一個房屋和最後一個房屋是緊挨着的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，能夠偷竊到的最高金額。 示例 1：

輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號房屋（金額 = 2），然後偷竊 3 號房屋（金額 = 2）, 因爲他們是相鄰的。

示例 2：

輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 號房屋（金額 = 1），然後偷竊 3 號房屋（金額 = 3）。
     偷竊到的最高金額 = 1 + 3 = 4 。

示例 3：

輸入：nums = [0]
輸出：0

提示：

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 1000

打家劫舍這類問題其實都可以使用動態規劃來解答，這個題目和打家劫舍類似，不過就是多了兩種情況：

• 不偷第一家

• 不偷最後一家

這樣就可以分類討論，當不偷第一家時，就排除到第一家，對其他家進行計算，當不偷最後一家時，就排除掉最後一家，對其他家進行計算。

當前節點的最大值就是當前節點和之前的第二個節點的和與上個節點的值的最大值，這樣說可能比較繞，狀態轉移方程代碼：

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

代碼實現：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length
    let res1 = 0, res2 = 0
    if(len === 0) return 0
    if(len === 1) return nums[0]

    const dp = new Array(len)
    
    // 不偷第一家
    dp[0] = 0
    dp[1] = nums[1]
    for(let i = 2; i <= len - 1; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res1 = dp[len - 1]

    // 不偷最後一家
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for(let i = 2; i <= len - 2; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res2 = dp[len - 2]
    return Math.max(res1, res2)
};

複雜度分析：

• 時間複雜度：O(n)，其中 n 是數組的長度，我們需要遍歷兩次數組；

• 空間複雜度：O(n)，其中 n 是數組的長度，我們需要初始化一個長度爲 n 的數組來保存當前節點的狀態。

3. 打家劫舍 III

在上次打劫完一條街道之後和一圈房屋後，小偷又發現了一個新的可行竊的地區。這個地區只有一個入口，我們稱之爲 “根”。除了“根” 之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之後，聰明的小偷意識到“這個地方的所有房屋的排列類似於一棵二叉樹”。如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。示例 1:

輸入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
輸出: 7 
解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7.

示例 2:

輸入: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
輸出: 9
解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.

對於這道題目，可以使用動態規劃來解答。

對於二叉樹，每個節點都有兩種狀態，選中或者不選中，我們可以使用深度優先遍歷來遍歷這棵二叉樹：

• 當節點被選中時，它的左右孩子都不能被選中，所以最大值就是：node.val + left[1] + right[1]；

• 當節點不被選中時，它的左右子孩子可以選中也可以不選中，所以最大值就是：Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

最後返回左右子樹中最大值即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const dfs = (node) => {
        if (node === null) {
            return [0, 0];
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
      
        const select = node.val + left[1] + right[1];
        const notSelect = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [select, notSelect];
    }
    const res = dfs(root)
    return Math.max(res[0], res[1])
};

複雜度分析：

• 時間複雜度：O(n)，對二叉樹進行了一次後序遍歷，所以時間複雜度是 O(n)；

• 空間複雜度：O(n)，遞歸棧空間的使用代價是 O(n)。

五、LeetCode 迴文串問題

1. 迴文子串

給定一個字符串，你的任務是計算這個字符串中有多少個迴文子串。具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。

示例 1：

輸入："abc"
輸出：3
解釋：三個迴文子串: "a", "b", "c"

示例 2：

輸入："aaa"
輸出：6
解釋：6個迴文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：輸入的字符串長度不會超過 1000 。

這個題目最直接的方法就是使用暴力循環來解決，遍歷每一種可能，具體思路如下：

• 首先，根據題目，我們可以看出，每個元素自身也算是一個迴文子串，所以要將字符串的長度加進去

• 定義一個函數用來檢測字符串是否是迴文串

• 兩層遍歷字符串，截取字符串的所有的子串，並判斷其是否是迴文串

複雜度分析：

• 時間複雜度爲 O(n2)，需要兩層遍歷。

• 空間複雜度爲 O(1)

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = s.length
    let len = s.length
    for(let i = 0; i < len; i++){
        for(let j = i + 1; j < len; j++){
            let temp = s.substr(i, j-i+1)
            if(isSub(temp)){
                count++
            }
        }
    }
    return count
};
const isSub = str => {
        let a = 0
        let b = str.length - 1
        while(a <= b){
            if(str[a] !== str[b]){
                return false
            }
            a++
            b--
        }
        return true
    }

2. 最長迴文子串

給定一個字符串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度爲 1000。示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

這裏使用兩種方法來解答這個問題：（1）方法一：中心擴展法中心擴展法的思想就是枚舉出可能出現的迴文串的中心，從這個中心位置儘可能的向兩邊擴散出去，得到一個迴文串，具體實現步驟如下：

• 選取對稱中心（奇數長度的字符串爲中心兩個字符的中間，偶數長度的字符串中心爲中間的字符）

• 通過對比擴展之後得出的兩種組合較大的迴文子串長度

• 對比之前的長度，判斷是否更新起始的位置

• 遍歷完之後，根據起始位置，截取最長迴文子串

代碼實現：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s == null || s.length <1){
        return ''
    }
    let start = 0
    let end = 0
    // 定義中心擴展的方法
    const fn = (s,left,right) => {
        while(left >=0 && right< s.length && s[left] === s[right]){
            left--
            right++
        }
        return right - left -1
    }
    // 遍歷字符串
    for(let i = 0; i<s.length; i++){
        const len1 = fn(s, i, i)
        const len2 = fn(s, i, i+1)
        const len = Math.max(len1, len2)
        // 判斷起始位置是否更新
        if(len > end - start){
            start = i- Math.floor((len-1)/2)
            end = i+ Math.floor(len/2)
        }
    }
    return s.substring(start, end+1)
};

複雜度分析：

• 時間複雜度：O(n2)，枚舉 “中心位置” 時間複雜度爲 O(n)，從 “中心位置” 擴散得到 “迴文子串” 的時間複雜度爲 O(n)，因此時間複雜度是 O(n2)。

• 空間複雜度：O(1)，這裏只用到了兩個常數臨時變量 start、end，因此空間複雜度爲 O(1)。

（2）方法二：動態規劃解決這類問題的核心思想就是兩個字 “延伸”，具體來說

• 如果一個字符串是迴文串，那麼在它左右分別加上一個相同的字符，那麼它一定還是一個迴文串

• 如果在一個不是迴文字符串的字符串兩端添加任何字符，或者在迴文串左右分別加不同的字符，得到的一定不是迴文串

事實上，上面的分析已經建立了大問題和小問題之間的關聯，因爲我們可以建立動態規劃模型。可以用 dp[i][j] 表示 s 中從 i 到 j（包括 i 和 j）是否可以形成迴文，狀態轉移方程只是將上面的描述轉化爲代碼即可：

if (s[i] === s[j] && dp[i + 1][j - 1]) {
  dp[i][j] = true;
}

其中：

• s[i] === s[j]：說明當前中心可以繼續擴張，進而有可能擴大回文串的長度

• dp[i+1][j-1]：true，說明 s[i,j] 的子串 s[i+1][j-1] 也是迴文串，其中，i 是從最大值開始遍歷的，j 是從最小值開始遍歷的

總結一下，使用動態規劃的具體實現步驟如下：

• 確定 dp[i][j] 是否是迴文數，只需要 dp[i+1][j-1] 是迴文數並且 s[i] === s[j] 即可。

• 長度爲 0 或 1 的迴文傳需要特殊處理，即 j-i < 2;

• 因爲知道 dp[i] 需要先知道 dp[i+1]，所以 i 需要從大到小開始遍歷

• 因爲知道 dp[j] 需要先知道 dp[j-1]，所以 j 需要從小到大開始遍歷

代碼實現：

 /**
 * @param {string} s
 * @return {string}
 */
// 擴展中心
var longestPalindrome = function(s) {
   let res = '';
    let n = s.length;
    let dp = Array.from(new Array(n), () => new Array().fill(0));
    
    for(let i = n-1; i >=0; i--) {
        for(let j = i; j < n; j++) {
            dp[i][j] = s[i] === s[j] && ( j - i < 2 || dp[i+1][j-1])
            if(dp[i][j] && j - i + 1 > res.length) {
                res = s.substr(i,j - i + 1);
            }
        }
    }
    return res;
}

複雜度分析：

• 時間複雜度：O(n2)，其中 n 是字符串的長度。動態規劃的狀態總數爲 O(n2)，對於每個狀態，需要轉移的時間爲 O(1)。

• 空間複雜度：O(n2)，即存儲動態規劃狀態需要的空間。

3. 最長迴文子序列

給定一個字符串 s ，找到其中最長的迴文子序列，並返回該序列的長度。可以假設 s 的最大長度爲 1000 。 示例 1:

輸入: "bbbab"
輸出: 4
一個可能的最長迴文子序列爲 "bbbb"。

示例 2:

輸入: "cbbd"
輸出: 2
一個可能的最長迴文子序列爲 "bb"。

提示：

• 1 <= s.length <= 1000

• s 只包含小寫英文字母

對於這種迴文子串的問題，我們可以考慮能否使用動態規劃來求解。

這裏我們嘗試使用動態規劃來解答，初始化一個 dp 二維數組來保存子串的長度，dp[i][j] 表示 s 中的第 i 個字符到第 j 個字符組成的子串中，最長的迴文序列的長度。

下面最重要的就是找出狀態轉移方程：

• 如果字符串 s 的第 i 個和第 j 個字符相同：f[i][j] = f[i + 1][j - 1] + 2

• 如果字符串 s 的第 i 個和第 j 個字符不相同：f[i][j] = max(f[i + 1][j], f[i][j - 1])

這裏需要注意遍歷時的順序，i 是從最後一個字符開始遍歷的，j 是從 i+1 開始向後遍歷，這樣就能保證每個子問題都計算好了。最後只要返回dp[0][len-1]即可。

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    let len = s.length;
    
    let dp = new Array(len)
    for (let i = 0; i < len; i++) {
        dp[i] = new Array(len).fill(0);
    }
    
    for (let i = len - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i+1; j < len; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
            }
        }
    }
    return dp[0][len-1];
};

複雜度分析：

• 時間複雜度：O(n2)，其中 n 是字符串的長度，我們需要一個雙層的遍歷；

• 空間複雜度：O(n2)，其中 n 是字符串的長度，我們需要初始化一個二維數組。

六、LeetCode 子序列問題

1. 最大子序和

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，爲 6。

進階: 如果你已經實現複雜度爲 O(n) 的解法，嘗試使用更爲精妙的分治法求解。

**動態規劃求解：**通常我們遍歷子串或者子序列有三種遍歷方式

• 以某個節點爲開頭的所有子序列: 如 [a]，[a, b]，[ a, b, c] ... 再從以 b 爲開頭的子序列開始遍歷 [b] [b, c]。

• 根據子序列的長度爲標杆，如先遍歷出子序列長度爲 1 的子序列，在遍歷出長度爲 2 的 等等。

• 以子序列的結束節點爲基準，先遍歷出以某個節點爲結束的所有子序列，因爲每個節點都可能會是子序列的結束節點，因此要遍歷下整個序列，如: 以 b 爲結束點的所有子序列: [a , b] [b] ，以 c 爲結束點的所有子序列: [a, b, c] [b, c] [ c ]。

其中，第一種方式通常會使用暴力方法的求解，第二種方式在上面第五題已將用到過了，重點是第三種方式：因爲可以產生遞推關係, 採用動態規劃時, 經常通過此種遍歷方式, 如揹包問題、最大公共子串 , 這裏的動態規劃解法也是以先遍歷出以某個節點爲結束節點的所有子序列的思路。

代碼實現：

var maxSubArray = function(nums) {
    let sum = 0, res = nums[0]
    for(let num of nums){
        sum > 0 ? sum += num : sum = num
        res = Math.max(sum, res)
    }
    return res
};

複雜度分析：

• 時間複雜度：O(n)，其中 n 爲 nums 數組的長度，只需要遍歷一遍數組即可求得答案。

• 空間複雜度：O(1)，只需要常數空間存放若干變量。

2. 最長遞增子序列

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其餘元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

示例 1：

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度爲 4 。

示例 2：

輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：

輸入：nums = [7,7,7,7,7,7,7]
輸出：1

提示：

• 1 <= nums.length <= 2500

• -104 <= nums[i] <= 104

進階：

• 你可以設計時間複雜度爲 O(n2) 的解決方案嗎？

• 你能將算法的時間複雜度降低到 O(n log(n)) 嗎?

碰到子序列的問題，我們最容易想到的就是動態規劃。首先初始化一個數組 dp 來保存每個子問題的最優解，dp[i] 表示數組前 n 的元素的最長連續子序列，最後返回所有子序列中最長的序列就可以了。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    const n = nums.length
    if(!n){
        return 0
    }

    let dp = new Array(n).fill(1)
    for(let i = 1; i < n; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};

複雜度分析：

• 時間複雜度：O(n)，其中 n 爲數組 nums 的長度。動態規劃的狀態數爲 n，計算狀態 dp[i] 時，需要 O(n) 的時間遍歷 dp[0…i−1] 的所有狀態，所以總時間複雜度爲 O(n)。

• 空間複雜度：O(n)，需要額外使用長度爲 n 的 dp 數組。

3. 乘積最大的子數組

給你一個整數數組 nums ，請你找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），並返回該子數組所對應的乘積。 示例 1:

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數組 [2,3] 有最大乘積 6。

示例 2:

輸入: [-2,0,-1]
輸出: 0
解釋: 結果不能爲 2, 因爲 [-2,-1] 不是子數組。

對於這道題目，我們可以使用動態規劃來解答。

我們只需要在遍歷數組時，不斷更新最大值即可，這個過程中，我們需要維護兩個值：

• max，當前的最大值，將當前的值與當前的值和之前的最大值的乘積進行對比，保存最大值

• min，當前的最小值，將當前的值與當前的值和之前的最小值的乘積進行對比，保存最小值

我們這裏求的是最大值，那爲啥還要保存最小值呢？這是因爲數組中可能會有負數，噹噹前的值是負數時，與之前的值相乘就會導致最大值和最小值交換，所以我們需要維護一個最大值和一個最小值。然後不斷使用當前的最大值保存爲結果，最後返回結果即可。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let res = -Infinity, max = 1, min = 1;

    for(let i = 0; i < nums.length; i++){
        if(nums[i] < 0){
            let temp = max
            max = min
            min = temp
        }
        max = Math.max(nums[i], nums[i] * max)
        min = Math.min(nums[i], nums[i] * min)

        res = Math.max(res, max)
    }
    return res
};

複雜度分析：

• 時間複雜度：O(n)，我們需要遍歷一遍數組，所以時間複雜度爲 O(n)；

• 空間複雜度：O(1)，這裏我們需要的額外空間爲常數級，所以空間複雜度爲 O(1)。

4. 最長重複子數組

給兩個整數數組 A 和 B ，返回兩個數組中公共的、長度最長的子數組的長度。 示例：

輸入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
輸出：3
解釋：
長度最長的公共子數組是 [3, 2, 1] 。

提示：

• 1 <= len(A), len(B) <= 1000

• 0 <= A[i], B[i] < 100

對於這道題目，我們可以使用動態規劃來解決。動態規劃就是要保持上一個狀態和下一個狀態有關係，並且是連續的。這裏的子數組就相當於子串，是連續的。

這裏我們初始化一個 dp 數組保存當前的最大連續值，dp[i][j] 表示數組 A 的前 i 個元素和數組 B 的前 j 個元素組成的最長公共子數組的長度。

在遍歷數組時：

• 如果當前的兩個元素的值相等，也就是 A[i] === B[j]，則說明當前的元素可以構成公共子數組，所以讓前一個元素的最長公共子數組的長度加一，此時的狀態轉移方程是：dp[i][j] = dp[i - 1][j - 1] + 1；

• 如果當前的兩個元素的值不相等，所以此時的 dp 值保存爲 0（初始化爲 0）。

在遍歷的過程中，不斷更新最長公共子序列最大值。

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var findLength = function(A, B) {
    const m = A.length, n = B.length;

    let dp = new Array(m + 1)
    for (let i = 0; i <= m; i++) { 
        dp[i] = new Array(n + 1).fill(0);
    }

    let res = 0

    for(let i = 1; i <= m; i++){
        for(let j = 1; j <= n; j++){
            if(A[i - 1] === B[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            res = Math.max(dp[i][j], res)
        }
    }
    return res
};

複雜度分析：

• 時間複雜度：O(mn)，其中 m 和 n 分別是 A 和 B 兩個數組的長度，這裏我們需要兩層遍歷兩個數組。

• 空間複雜度：O(mn)，其中 m 和 n 分別是 A 和 B 兩個數組的長度，我們需要初始化一個 dp 二維數組來保存當前的最長公共子數組的長度。

七、LeetCode 其他問題

1. 接雨水

給定 n 個非負整數表示每個寬度爲 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。

示例 1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。

示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

提示：

• n == height.length

• 0 <= n <= 3 * 104

• 0 <= height[i] <= 105

看到這道題，我們自然而然的可以想到木桶效應，每根柱子上的雨水的深度取決於它兩側最高的柱子中較短的那根柱子的長度。

• 如果這個較短的柱子的長度大於當前柱子，那麼雨水的深度就是較短的柱子減去當前柱子的長度；

• 如果這個較短的柱子的長度小於等於當前柱子，那麼雨水的深度就是 0。

對於下標 i，下雨後水能到達的最大高度等於下標 i 兩邊的最大高度的最小值，下標 i 處能接的雨水量等於下標 i 處的水能到達的最大高度減去 height[i]。

最直接的做法是對於數組 height 中的每個元素，分別向左和向右掃描並記錄左邊和右邊的最大高度，然後計算每個下標位置能接的雨水量。使用動態規劃的方法，可以在 O(n) 的時間內預處理得到每個位置兩邊的最大高度。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let len = height.length, sum = 0
    for(let i = 0; i < len - 1; i++){
        // 計算當前柱子左側的最大值
        let left = 0
        for(let j = i - 1; j >= 0; j--){
            left = Math.max(height[j], left)
        }
        // 計算當前柱子右側的最大值
        let right = 0
        for(let j = i + 1; j < len; j++){
            right = Math.max(height[j],right)
        }
        // 計算當前柱子能接的雨水量
        if(min > height[i]){
            sum += Math.min(left, right) - height[i]
        }
    }
    return sum
};

複雜度分析：

• 時間複雜度：O(n)，其中 n 是數組 height 的長度。需要遍歷兩次 height 數組；

• 空間複雜度：O(1)。

2. 爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意： 給定 n 是一個正整數。示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1.  1 階 + 1 階
2.  2 階

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階

看到這個題目，我們應該想到的就是動態規劃，將一個大問題分解成多個子問題。首先來看：

• 第一級臺階：1 種方法

• 第二級臺階：2 種方法

• 第 n 級臺階：從第 n-1 級臺階爬一級，或從第 n-2 級臺階爬 2 級

所以可以得出遞推公式：f(n) = f(n−1) + f(n−2) 這樣，我們就可以通過遞歸完成計算。

上面這種普通遞歸很顯然，有很多的重複計算，所以，我們可以將每次計算的結果進行保存，以便下次計算時直接使用。

普通遞歸：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for(let i = 2; i <= n; i ++){
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};

記憶遞歸：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let a = 1, b = 1, res = 1;
    for (let i = 1; i < n; i++) {
        a = b
        b = res
        res = a + b
    }
    return res
};

普通遞歸複雜度分析：

• 時間複雜度：O(n2)，遞歸樹的深度爲 n，所以時間複雜度爲 O(n2)；

• 空間複雜度：O(n)，這裏需要初始化一個數組用來保存每一層臺階的方法數，有 n 個數，所以空間複雜度爲 O(n)；

記憶遞歸複雜度分析：

• 時間複雜度：O(n)，需要循環執行 n 次，所以時間複雜度爲 O(n)；

• 空間複雜度：O(1)，這裏只用了常數個變量作爲輔助空間，所以空間複雜度爲 O(1)；

3. 最大正方形

在一個由 '0' 和 '1' 組成的二維矩陣內，找到只包含 '1' 的最大正方形，並返回其面積。

示例 1：

輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：4

示例 2：

輸入：matrix = [["0","1"],["1","0"]]
輸出：1

示例 3：

輸入：matrix = [["0"]]
輸出：0

提示：

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 300

• matrix[i][j] 爲 '0' 或 '1'

對於這道題目，可以使用動態規劃來解決，這裏我們需要初始化與一個 dp 數組，dp[i][i] 表示以 (i, j) 爲右下角，且只包含 1 的正方形的邊長最大值。我們只需要遍歷這個二維矩陣，計算機每個 dp 的值，選出最大值，即正方形的最大邊長，最後返回這個正方形的面積即可。

計算 dp 的每個值有以下規則：

• 如果當前的值爲 0，此時該點不存在於正方形中，直接給 dp[i][j] 賦值爲 0；

• 如果當前的值爲 1，dp[i][j] 的值由其上、左、左上的三個值的最小值決定，所以其狀態轉移方程是：

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

除此之外，我們還需要考慮二維矩陣的最左邊一列和最上面一行，如果值是 1，就直接將 dp[i][j] 賦值爲 1。

代碼實現：

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    const m = matrix.length, n = matrix[0].length
    let res = 0
    if(!matrix || m === 0 || n === 0){
        return 0
    }

    let dp = new Array(m)
    for(let i = 0; i < m; i++){
        dp[i] = new Array(n).fill(0)
    }

    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(matrix[i][j] === '1'){
                if(i === 0 || j === 0){
                    dp[i][j] = 1
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                }
                res = Math.max(dp[i][j], res)
            }
        }
    }
    return res * res
};

複雜度分析：

• 時間複雜度：O(mn)，其中 m 和 n 是二維矩陣的行數和列數。我們需要遍歷二維矩陣中的每個元素來計算 dp 的值。

• 空間複雜度：O(mn)，其中 m 和 n 是二維矩陣的行數和列數。我們創建了一個和原始矩陣大小相同的數組 dp 來保存當前正方形的最大邊長。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/tWwFK5M2cRCibEM1KHiitg