摘要：11 return dp[n]。所以 我們令  dp[n] 表示能到達第 n 階 的方法總數，可以得到如下狀態轉移方程：。

小浩：宜信科技中心攻城獅一枚，熱愛算法，熱愛學習，不拘泥於枯燥編程代碼，更喜歡用輕鬆方式把問題簡單闡述，希望喜歡的小夥伴可以多多關注！

動態規劃系列一： 爬樓梯

1.1 概念講解

講解動態規劃的資料很多，官方的定義是指把多階段過程轉化爲一系列單階段問題，利用各階段之間的關係，逐個求解。概念中的各階段之間的關係，其實指的就是狀態轉移方程。很多人覺得DP難（下文統稱動態規劃爲DP），根本原因是因爲DP區別於一些固定形式的算法（比如DFS、二分法、KMP），沒有實際的步驟規定第一步第二步來做什麼，所以準確的說，DP其實是一種解決問題的思想。

這種思想的本質是：一個規模比較大的問題（可以用兩三個參數表示的問題），可以通過若干規模較小的問題的結果來得到的（通常會尋求到一些特殊的計算邏輯，如求最值等）

所以我們一般看到的狀態轉移方程，基本都是這樣：

opt ： 指代特殊的計算邏輯，通常爲max or min。

i,j,k 都是在定義DP方程中用到的參數。

dp[i] = opt(dp[i-1])+1

dp[i][j] = w(i,j,k) + opt(dp[i-1][k])

dp[i][j] = opt(dp[i-1][j] + xi, dp[i][j-1] + yj, ...)

每一個狀態轉移方程，多少都有一些細微的差別。這個其實很容易理解，世間的關係多了去了，不可能抽象出完全可以套用的公式。所以我個人其實不建議去死記硬背各種類型的狀態轉移方程。但是DP的題型真的就完全無法掌握，無法歸類進行分析嗎？我認爲不是的。在本系列中，我將由簡入深爲大家講解動態規劃這個主題。

我們先看上一道最簡單的DP題目，熟悉DP的概念：

題目： 假設你正在爬樓梯。 需要 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 題目圖解

通過分析我們可以明確，該題可以被分解爲一些包含最優子結構的子問題，即它的 最優解可以從其子問題的最優解來有效地構建 。滿足 “ 將大問題分解爲若干個規模較小的問題 ”的條件。 所以 我們令  dp[n] 表示能到達第 n 階 的方法總數，可以得到如下狀態轉移方程：

dp[n]=dp[n-1]+dp[n-2]

  • 上 1 階臺階：有1種方式。

  • 上 2 階臺階：有1+1和2兩種方式。

  • 上 3 階臺階：到達第3階的方法總數就是到第1階和第2階的方法數之和。

  • 上 n 階臺階，到達第n階的方法總數就是到第 (n-1) 階和第 (n-2) 階的方法數之和。

1.3 Go語言示例

根據分析，得到代碼如下：

 1func climbStairs(n int) int {
 2    if n == 1 {
 3        return 1
 4    }
 5    dp := make([]int, n+1)
 6    dp[1] = 1
 7    dp[2] = 2
 8    for i := 3; i <= n; i++ {
 9        dp[i] = dp[i-1] + dp[i-2]
10    }
11    return dp[n]
12}

動態規劃系列二： 最大子序和

2.1 最大子序和

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

示 例 ：

輸入: [-2,1,-3,4,-1,2,1,-5,4],

輸出: 6

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

拿到題目請不要看下方題解，先自行思考2-3分鐘....

2.1 題目圖解

首先我們分析題目，一個連續子數組一定要以一個數作爲結尾，那麼我們可以將狀態定義成如下：

dp[i]： 表示以 nums[i] 結尾的連續子數組的最大和。

那麼爲什麼這麼定義呢？因爲這樣定義其實是最容易想到的！在上一節中我們提到，狀態轉移方程其實是通過1-3個參數的方程來描述小規模問題和大規模問題間的關係。

當然，如果你沒有想到，其實也非常正常！因爲 "該問題最早於 1977 年提出，但是直到 1984 年才被發現了線性時間的最優解法。" 

根據狀態的定義，我們繼續進行分析：

如果要得到dp[i]，那麼nums[i]一定會被選取。並且 dp[i] 所表示的連續子序列與 dp[i-1] 所表示的連續子序列很可能就差一個 nums[i] 。即 

dp[i] = dp[i-1]+nums[i] , if (dp[i-1] >= 0)

但是這裏我們遇到一個問題， 很有可能dp[i-1]本身是一個負數。 那這種情況的話， 如果dp[i]通過dp[i-1]+nums[i]來推導，那麼結果其實反而變小了，因爲我們dp[i]要求的是最大和。 所以在這種情況下，如果dp[i-1]<0，那麼dp[i]其實就是nums[i]的值。即

dp[i] = nums[i] , if (dp[i-1] < 0)

綜上分析，我們可以得到：

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

得到了狀態轉移方程，但是我們還需要通過一個已有的狀態的進行推導，我們可以想到  dp[0] 一定是以 nums[0] 進行結尾 ，所以 

dp[0] = nums[0]

在很多題目中，因爲dp[i]本身就定義成了題目中的問題，所以dp[i]最終就是要的答案。但是這裏狀態中的定義，並不是題目中要的問題，不能直接返回最後的一個狀態 (這一步經常有初學者會摔跟頭)。所以最終的答案，其實我們是尋找：

max(dp[0], dp[1], ..., d[i-1], dp[i])

分析完畢，我們繪製成圖：

假定 nums 爲  [-2,1,-3,4,-1,2,1,-5,4]

2.3 Go語言示例

根據分析，得到代碼如下：

 1func maxSubArray(nums []int) int {
 2    if len(nums) < 1 {
 3        return 0
 4    }
 5    dp := make([]int, len(nums))
 6    //設置初始化值 
 7    dp[0] = nums[0]
 8    for i := 1; i < len(nums); i++ {
 9        //處理 dp[i-1] < 0 的情況
10        if dp[i-1] < 0 {
11            dp[i] = nums[i]
12        } else {
13            dp[i] = dp[i-1] + nums[i]
14        }
15    }
16    result := -1 << 31
17    for _, k := range dp {
18        result = max(result, k)
19    }
20    return result
21}
22
23func max(a, b int) int {
24    if a > b {
25        return a
26    }
27    return b
28}

我們可以進一步精簡代碼爲：

 1func maxSubArray(nums []int) int {
 2    if len(nums) < 1 {
 3        return 0
 4    }
 5    dp := make([]int, len(nums))
 6    result := nums[0]
 7    dp[0] = nums[0]
 8    for i := 1; i < len(nums); i++ {
 9        dp[i] = max(dp[i-1]+nums[i], nums[i])
10        result = max(dp[i], result)
11    }
12    return result
13}
14
15func max(a, b int) int {
16    if a > b {
17        return a
18    }
19    return b
20}

複雜度分析：時間複雜度：O(N)。空間複雜度：O(N)。

動態規劃系列三： 最長上升子序列

3.1 最長上升子序列

題目： 給定一個無序的整數數組，找到其中最長上升子序列的長度。

示例:

輸入: [10,9,2,5,3,7,101,18]

輸出: 4 

解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。

說明:

可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。

本題有一定難度！

如果沒有思路請回顧上一篇的學習內容！

不建議直接看題解！

3.2  題目圖解

首先我們分析題目，要找的是最長上升子序列（Longest Increasing Subsequence，LIS）。因爲題目中沒有要求連續，所以LIS可能是連續的，也可能是非連續的。同時，LIS符合可以從其子問題的最優解來進行構建的條件。所以我們可以嘗試用動態規劃來進行求解。首先我們定義狀態：

dp[i] ： 表示以nums[i]結尾的最長上升子序列的長度

我們假定nums爲[1，9，5，9，3]

我們分兩種情況進行討論：

  • 如果nums[i]比前面的所有元素都小，那麼dp[i]等於1（即它本身）（該結論正確）

  • 如果nums[i]前面存在比他小的元素nums[j]，那麼dp[i]就等於dp[j]+1（ 該結論錯誤，比如nums[3]>nums[0]，即9>1,但是dp[3]並不等於dp[0]+1 ）

我們先初步得出上面的結論，但是我們發現了一些問題。因爲dp[i]前面比他小的元素，不一定只有一個！

可能除了nums[j]，還包括nums[k]，nums[p] 等等等等。所以dp[i]除了可能等於dp[j]+1，還有可能等於dp[k]+1，dp[p]+1 等等等等。所以我們求dp[i]，需要找到dp[j]+1，dp[k]+1，dp[p]+1 等等等等中的最大值。（我在3個等等等等上都進行了加粗，主要是因爲初學者非常容易在這裏摔跟斗！這裏強調的目的是希望能記住這道題型！）

即：

dp[i] = max(dp[j]+1，dp[k]+1，dp[p]+1，.....)

只要滿足：

nums[i] > nums[j]

nums[i] > nums[k]

nums[i] > nums[p]

....

最後，我們只需要找到dp數組中的最大值，就是我們要找的答案。

分析完畢，我們繪製成圖：

3.3 Go語言示例

根據分析，得到代碼如下：

 1func lengthOfLIS(nums []int) int {
 2    if len(nums) < 1 {
 3        return 0
 4    }
 5    dp := make([]int, len(nums))
 6    result := 1
 7    for i := 0; i < len(nums); i++ {
 8        dp[i] = 1
 9        for j := 0; j < i; j++ {
10            //這行代碼就是上文中那個 等等等等
11            if nums[j] < nums[i] {
12                dp[i] = max(dp[j]+1, dp[i])
13            }
14        }
15        result = max(result, dp[i])
16    }
17    return result
18}
19
20func max(a, b int) int {
21    if a > b {
22        return a
23    }
24    return b
25}

動態規劃系列四： 三角形最小路徑和

前面章節我們通過題目“最長上升子序列”以及"最大子序和"，學習了DP（動態規劃）在線性關係中的分析方法。這種分析方法，也在運籌學中被稱爲“線性動態規劃”，具體指的是 “目標函數爲特定變量的線性函數，約束是這些變量的線性不等式或等式，目的是求目標函數的最大值或最小值”。這點大家作爲了解即可，不需要死記，更不要生搬硬套！

在本節中，我們將繼續分析一道略微區別於之前的題型，希望可以由此題與之前的題目進行對比論證，進而順利求解！

4.1 三角形最小路徑和

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

示例:

每一步只能移動到下一行中相鄰的結點上。

例如，給定三角形：

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

自頂向下的最小路徑和爲 11（即，2 + 3 + 5 + 1 = 11）。

4.2 自頂向下圖解分析

首先我們分析題目，要找的是 三角形最小路徑和 ，這是個啥意思呢？假設我們有一個三角形：[[2], [3,4], [6,5,7], [4,1,8,3]]

那從上到下的最小路徑和就是2-3-5-1，等於11。

由於我們是使用數組來定義一個三角形，所以便於我們分析，我們將三角形稍微進行改動：

這樣相當於我們將整個三角形進行了拉伸。這時候，我們根據題目中給出的條件：每一步只能移動到下一行中相鄰的結點上。其實也就等同於，每一步我們只能往下移動一格或者右下移動一格。將其轉化成代碼，假如2所在的元素位置爲[0,0]，那我們往下移動就只能移動到[1,0]或者[1,1]的位置上。假如5所在的位置爲[2,1]，同樣也只能移動到[3,1]和[3,2]的位置上。如下圖所示：

題目明確了之後，現在我們開始進行分析。題目很明顯是一個找最優解的問題，並且可以從子問題的最優解進行構建。所以我們通過動態規劃進行求解。首先，我們定義狀態：

dp[i][j] : 表示包含第i行j列元素的最小路徑和

我們很容易想到可以自頂向下進行分析。並且，無論最後的路徑是哪一條，它一定要經過最頂上的元素，即[0,0]。所以我們需要對dp[0][0]進行初始化。

dp[0][0] = [0][0]位置所在的元素值

繼續分析，如果我們要求dp[i][j]，那麼其一定會從自己頭頂上的兩個元素移動而來。

如5這個位置的最小路徑和，要麼是從2-3-5而來，要麼是從2-4-5而來。然後取兩條路徑和中較小的一個即可。進而我們得到狀態轉移方程：

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

但是，我們這裏會遇到一個問題！除了最頂上的元素之外，

最左邊的元素只能從自己頭頂而來。（2-3-6-4）

最右邊的元素只能從自己左上角而來。（2-4-7-3）

然後，我們觀察發現，位於第2行的元素，都是特殊元素（因爲都只能從[0,0]的元素走過來）

我們可以直接將其特殊處理，得到：

dp[1][0] = triangle[1][0] + triangle[0][0]

dp[1][1] = triangle[1][1] + triangle[0][0]

最後，我們只要找到最後一行元素中，路徑和最小的一個，就是我們的答案。即：

l：dp數組長度

result = min(dp[l-1,0]，dp[l-1,1]，dp[l-1,2]....)

綜上我們就分析完了，我們總共進行了4步：

  1. 定義狀態

  2. 總結狀態轉移方程

  3. 分析狀態轉移方程不能滿足的特殊情況。

  4. 得到最終解

4.3 代碼分析

分析完畢，代碼自成：

 1func minimumTotal(triangle [][]int) int {
 2    if len(triangle) < 1 {
 3        return 0
 4    }
 5    if len(triangle) == 1 {
 6        return triangle[0][0]
 7    }
 8    dp := make([][]int, len(triangle))
 9    for i, arr := range triangle {
10        dp[i] = make([]int, len(arr))
11    }
12    result := 1<<31 - 1
13    dp[0][0] = triangle[0][0]
14    dp[1][1] = triangle[1][1] + triangle[0][0]
15    dp[1][0] = triangle[1][0] + triangle[0][0]
16    for i := 2; i < len(triangle); i++ {
17        for j := 0; j < len(triangle[i]); j++ {
18            if j == 0 {
19                dp[i][j] = dp[i-1][j] + triangle[i][j]
20            } else if j == (len(triangle[i]) - 1) {
21                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
22            } else {
23                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
24            }
25        }  
26    }
27    for _,k := range dp[len(dp)-1] {
28        result = min(result, k)
29    }
30    return result
31}
32
33func min(a, b int) int {
34    if a > b {
35        return b
36    }
37    return a
38}

運行上面的代碼，我們發現使用的內存過大。我們有沒有什麼辦法可以壓縮內存呢？通過觀察我們發現 ，在我們自頂向下的過程中，其實我們只需要使用到上一層中已經累積計算完畢的數據，並且不會再次訪問之前的元素數據。 繪製成圖如下：

優化後的代碼如下：

 1func minimumTotal(triangle [][]int) int {
 2    l := len(triangle)
 3    if l < 1 {
 4        return 0
 5    }
 6    if l == 1 {
 7        return triangle[0][0]
 8    }
 9    result := 1<<31 - 1
10    triangle[0][0] = triangle[0][0]
11    triangle[1][1] = triangle[1][1] + triangle[0][0]
12    triangle[1][0] = triangle[1][0] + triangle[0][0]
13    for i := 2; i < l; i++ {
14        for j := 0; j < len(triangle[i]); j++ {
15            if j == 0 {
16                triangle[i][j] = triangle[i-1][j] + triangle[i][j]
17            } else if j == (len(triangle[i]) - 1) {
18                triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
19            } else {
20                triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]
21            }
22        }  
23    }
24    for _,k := range triangle[l-1] {
25        result = min(result, k)
26    }
27    return result
28}
29
30func min(a, b int) int {
31    if a > b {
32        return b
33    }
34    return a
35}

動態規劃系列五： 最小路徑和

在上節中，我們通過分析，順利完成了“三角形最小路徑和”的動態規劃題解。在本節中，我們繼續看一道相似題型，以求能完全掌握這種“路徑和”的問題。話不多說，先看題目：

5.1 最小路徑和

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

示例:

輸入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

輸出: 7

解釋: 因爲路徑 1→3→1→1→1 的總和最小。

5.2 圖解分析

首先我們分析題目，要找的是 最小路徑和，這是個啥意思呢？假設我們有一個 m*n 的矩形 ：[[1,3,1],[1,5,1],[4,2,1]]

那從左上角到右下角的最小路徑和，我們可以很容易看出就是1-3-1-1-1，這一條路徑，結果等於7。

題目明確了，我們繼續進行分析。該題與上一道求三角形最小路徑和一樣，題目明顯符合可以從子問題的最優解進行構建，所以我們考慮使用動態規劃進行求解。首先，我們定義狀態：

dp[i][j] : 表示包含第i行j列元素的最小路徑和

同樣，因爲任何一條到達右下角的路徑，都會經過[0,0]這個元素。所以我們需要對dp[0][0]進行初始化。

dp[0][0] = [0][0]位置所在的元素值

繼續分析，根據題目給的條件，如果我們要求dp[i][j]，那麼它一定是從自己的上方或者左邊移動而來。如下圖所示：

  • 5，只能從3或者1移動而來

  • 2，只能從5或者4移動而來

  • 4，從1移動而來

  • 3，從1移動而來

  • 紅色位置必須從藍色位置移動而來

進而我們得到狀態轉移方程：

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

同樣我們需要考慮兩種特殊情況：

  • 最上面一行，只能由左邊移動而來（1-3-1）

  • 最左邊一列，只能由上面移動而來（1-1-4）

最後，因爲我們的目標是從左上角走到右下角，整個網格的最小路徑和其實就是包含右下角元素的最小路徑和。即：

設：dp的長度爲l

最終結果就是：dp[l-1][len(dp[l-1])-1]

綜上我們就分析完了，我們總共進行了4步：

  1. 定義狀態

  2. 總結狀態轉移方程

  3. 分析狀態轉移方程不能滿足的特殊情況。

  4. 得到最終解

5.3 代碼分析

分析完畢，代碼自成：

 1func minPathSum(grid [][]int) int {
 2    l := len(grid)
 3    if l < 1 {
 4        return 0
 5    }
 6    dp := make([][]int, l)
 7    for i, arr := range grid {
 8        dp[i] = make([]int, len(arr))
 9    }
10    dp[0][0] = grid[0][0]
11    for i := 0; i < l; i++ {
12        for j := 0; j < len(grid[i]); j++ {
13            if i == 0 && j != 0 {
14                dp[i][j] = dp[i][j-1] + grid[i][j]
15            } else if j == 0 && i != 0 {
16                dp[i][j] = dp[i-1][j] + grid[i][j]
17            } else if i != 0 && j != 0 {
18                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
19            }
20        }
21    }
22    return dp[l-1][len(dp[l-1])-1]
23}
24
25func min(a, b int) int {
26    if a > b {
27        return b
28    }
29    return a
30}

同樣，運行上面的代碼，我們發現使用的內存過大。有沒有什麼辦法可以壓縮內存呢？通過觀察我們發現 ，在我們自左上角到右下角計算各個節點的最小路徑和的過程中，我們只需要使用到之前已經累積計算完畢的數據 ，並且不會再次訪問之前的元素數據。繪製成圖如下：(大家看這個過程像不像掃雷，其實如果大家研究掃雷外掛的話，就會發現在掃雷的核心算法中，就有一處頗爲類似這種分析方法，這裏就不深究了)

優化後的代碼如下：

 1func minPathSum(grid [][]int) int {
 2    l := len(grid)
 3    if l < 1 {
 4        return 0
 5    }
 6    for i := 0; i < l; i++ {
 7        for j := 0; j < len(grid[i]); j++ {
 8            if i == 0 && j != 0 {
 9                grid[i][j] = grid[i][j-1] + grid[i][j]
10            } else if j == 0 && i != 0 {
11                grid[i][j] = grid[i-1][j] + grid[i][j]
12            } else if i != 0 && j != 0 {
13                grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
14            }
15        }
16    }
17    return grid[l-1][len(grid[l-1])-1]
18}
19
20func min(a, b int) int {
21    if a > b {
22        return b
23    }
24    return a
25}

本系列所有教程中都不會用到複雜的語言特性，大家不需要擔心沒有學過go。算法思想最重要，使用go純屬作者愛好。

原文首發於公衆號-小浩講算法

:star:️:star:️:star:️歡迎加入“ 宜信技術交流羣 ”。進羣方式：請加小助手微信（ 微信號：18910316664 ）。

◆  ◆  ◆  ◆  ◆

如需轉載請與小助手 （微信號： 18910316664 ）聯繫。 發現文章有錯誤、對內容有疑問，都可以通過關注宜信技術學院微信公衆號（ CE_TECH ），在後臺留言給我們。 我們每週會挑選出一位熱心小夥伴，送上一份精美的小禮品。 快來掃碼關注我們吧！

:arrow_double_down: 點擊“閱讀原文”查看更多技術乾貨

相關文章