小浩：宜信科技中心攻城狮一枚，热爱算法，热爱学习，不拘泥于枯燥编程代码，更喜欢用轻松方式把问题简单解决，希望喜欢的小伙伴可以多多关注！

动态规划系列一：爬楼梯

1.1概念讲解

讲解动态规划的资料很多，官方的定义是指把多阶段过程转化为串联单阶段问题，利用各阶段之间的关系，逐个替换。概念中的各阶段之间的关系，其实指的就是状态转移方程。很多人觉得DP难（内部统称动态规划为DP），根本原因是因为DP区别于一些固定形式的算法（称为DFS，二分法，KMP），没有实际的步骤规定步来做什么，所以准确的说，DP其实是一种解决问题的思想。

这种思想的本质是：一个规模比较大的问题（可以用两个三个参数表示的问题），可以通过某些规模较小的问题的结果来得到的（通常会寻求到一些特殊的计算逻辑，如求值等）

所以我们一般看到的状态转移方程，基本都是这样：

opt：指代特殊的计算逻辑，通常为max或min。

i，j，k都是在DPDP中用到的参数。

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]的表示能到达第ñ阶的方法总数，可以得到如下状态转移方程：

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语言范例

根据分析，得到代码如下：

func climbStairs(n int) int {
    if n == 1 {
        return 1
     }
     dp := make([]int, n+1)
     dp[1] = 1
     dp[2] = 2
     for i := 3; i <= n; i++ {
         dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

动态规划系列二：大子序和

2.1大子序和

译文：给定一个整数整数nums，找到一个具有大和的连续子数组（子重复少包含一个元素），返回其大和。

示例：

输入：[-2,1，-3,4，-1,2,1，-5,4]，

输出：6

解释：连续子分布[4，-1,2,1]的和大，为6。

拿到译文请不要看下方题解，先自行思考2-3分钟....

2.2译文图解

首先我们分析译文，一个连续子离散一定要以一个数作为结尾，那么我们可以将状态定义成如下：

dp [i]：表示以nums [i]结尾的连续子数组的大和。

那么为什么这么定义呢？因为这样定义其实是容易想到的！在上段中我们提到，状态转移方程实际上是通过1-3个参数的方程来描述小规模问题和大规模问题间的关系。

当然，如果您没有想到，实际上也非常正常！因为“该问题初于1977年提出，但是直到1984年才被发现了线性时间的优解法。” 

根据状态的定义，我们继续进行分析：

和dp [i]所表示的连续子序列与dp [i-1]所表示的连续子序列很可能就差一个nums [i]，如果要得到dp [i]，那么nums [i]一定会被挑选。 ]。即 

如果（dp [i-1]> = 0），则dp [i] = dp [i-1] + nums [i]

但是这里我们遇到一个问题，很有可能dp [i-1]本身是一个负数。那这种情况的话，如果dp [i]通过dp [i-1] + nums [i]来推导，那么结果其实反而变小了，因为我们dp [i]要求的是大和。所以在这种情况下，如果dp [i-1] <0，那么dp [i]其实就是nums [i]的值。即

如果（dp [i-1] <0），则dp [i] = nums [i]

综上分析，我们可以得到：

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语言范例

根据分析，得到代码如下：

func maxSubArray(nums []int) int {
    if len(nums) < 1 {
        return 
    }
    dp := make([]int, len(nums))
    //设置初始化值 
    dp[] = nums[]
    for i := 1; i < len(nums); i++ {
        //处理 dp[i-1] <  的情况
        if dp[i-1] <  {
            dp[i] = nums[i]
        } else {
            dp[i] = dp[i-1] + nums[i]
        }
    }
    result := -1 << 31
    for _, k := range dp {
        result = max(result, k)
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

我们可以进一步精简代码为：

func maxSubArray(nums []int) int {
    if len(nums) < 1 {
        return 
    }
    dp := make([]int, len(nums))
    result := nums[]
    dp[] = nums[]
    for i := 1; i < len(nums); i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        result = max(dp[i], result)
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析：时间复杂度：O（N）。空间复杂度：O（N）。

动态规划系列三：长上升子序列

3.1长上升子序列

译文：给定一个无序的整数副本，找到其中大上升子序列的长度。

示例：

输入：[10,9,2,5,3,7,101,18]

输出：4 

解释：长的上升子序列是[2,3,7,101]，它的长度是4。

说明：可能会有多个长上升子序列的组合，你只需要输出对应的长度即可。

本题有一定难度！

如果没有思路请回顾上一篇的学习内容！

不建议直接看题解！

3.2译文图解

首先我们分析译文，要找的是大上升子序列（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]前面比他小的元素，不一定只有一个！

所以dp [i]除了可能等于dp [j] +1，还有可能等于dp [k] + 1，dp可能还有除nums [j]，还包括nums [k]，nums [p]等等等等。 [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语言范例

根据分析，得到代码如下：

func lengthOfLIS(nums []int) int {
    if len(nums) < 1 {
        return 
    }
    dp := make([]int, len(nums))
    result := 1
    for i := ; i < len(nums); i++ {
        dp[i] = 1
        for j := ; j < i; j++ {
            //这行代码就是上文中那个 等等等等
            if nums[j] < nums[i] {
                dp[i] = max(dp[j]+1, dp[i])
            }
        }
        result = max(result, dp[i])
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

动态规划系列四：三角形小路径和

前面章节我们通过过渡“大上升子序列”以及“大子序和”，学习了DP（动态规划）在线性关系中的分析方法。这种分析方法，同时运筹学中被称为“线性”动态规划”，具体指的是“目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的替代或替代”。这点大家作为了解即可，不需要死记，更不要生搬硬套！

在本节中，我们将继续分析一道略微区别于之前的题型，希望可以通过标题与之前的译文进行对比对比证，长长的替换！

4.1三角形小路径和

译文：给定一个三角形，找出自顶向下的小路径和。

示例：

每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

自顶向下的小路径和为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]）+三角形[i] [j]

但是，我们这里会遇到一个问题！除了顶上的元素之外，

（2-3-6-4）左边的元素只能从自己头顶而来。（2-3-6-4）

（2-4-7-3）右边的元素只能从自己左上角而来。（2-4-7-3）

然后，我们观察发现，位于第2行的元素，都是特殊元素（因为都只能从[0,0]的元素走过来）

我们可以直接将其特殊处理，得到：

dp [1] [0] =三角形[1] [0] +三角形[0] [0]

dp [1] [1] =三角形[1] [1] +三角形[0] [0]

后，我们只要找到后一行元素中，路径和小的一个，就是我们的答案。即：

l：dp长度

结果= min（dp [l-1,0]，dp [l-1,1]，dp [l-1,2] ....）

综上我们就分析完了，我们总共进行了4步：

• 定义状态
• 总结状态转移方程
• 分析状态转移方程不能满足的特殊情况。
• 得到终解

4.3代码分析

分析完成，代码自成：

func minimumTotal(triangle [][]int) int {
    if len(triangle) < 1 {
        return 
    }
    if len(triangle) == 1 {
        return triangle[][]
    }
    dp := make([][]int, len(triangle))
    for i, arr := range triangle {
        dp[i] = make([]int, len(arr))
    }
    result := 1<<31 - 1
    dp[][] = triangle[][]
    dp[1][1] = triangle[1][1] + triangle[][]
    dp[1][] = triangle[1][] + triangle[][]
    for i := 2; i < len(triangle); i++ {
        for j := ; j < len(triangle[i]); j++ {
            if j ==  {
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            } else if j == (len(triangle[i]) - 1) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            } else {
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
            }
        }  
    }
    for _,k := range dp[len(dp)-1] {
        result = min(result, k)
    }
    return result
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

通过上述我们发现，在我们自顶向下的过程中，其实我们只需要使用到上一层中已经累积计算完成的数据，并且不会再次访问之前的元素数据。重置成图如下：

优化后的代码如下：

func minimumTotal(triangle [][]int) int {
    l := len(triangle)
    if l < 1 {
        return 
    }
    if l == 1 {
        return triangle[][]
    }
    result := 1<<31 - 1
    triangle[][] = triangle[][]
    triangle[1][1] = triangle[1][1] + triangle[][]
    triangle[1][] = triangle[1][] + triangle[][]
    for i := 2; i < l; i++ {
        for j := ; j < len(triangle[i]); j++ {
            if j ==  {
                triangle[i][j] = triangle[i-1][j] + triangle[i][j]
            } else if j == (len(triangle[i]) - 1) {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
            } else {
                triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]
            }
        }  
    }
    for _,k := range triangle[l-1] {
        result = min(result, k)
    }
    return result
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

动态规划系列五：小路径和

在上节中，我们通过分析，顺利完成了“三角形小路径和”的动态规划题解。在本节中，我们继续看一道相似题型，以求能完全掌握这种“路径和”的问题。话不多说，先看译文：

5.1小路径和

译文：给定一个包含非负整数的mxn网格，请找出一条从左上角到右下角的路径，从而路径上的数字总和为小。说明：每次只能向下或向右移动一步。

示例：

输入：

[

[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]）+格网[i] [j]

同样我们需要考虑两种特殊情况：

• 上面一行，只能由左边移动而来（1-3-1）
• 左边一列，只能由上面移动而来（1-1-4）

后，因为我们的目标是从左上角走到右下角，整个网格的小路径和实际上就是包含右下角元素的小路径和。即：

设：dp的长度为l

终结果就是：dp [l-1] [len（dp [l-1]）-1]

综上我们就分析完了，我们总共进行了4步：

• 定义状态
• 总结状态转移方程
• 分析状态转移方程不能满足的特殊情况。
• 得到终解

5.3代码分析

分析完成，代码自成：

func minPathSum(grid [][]int) int {
    l := len(grid)
    if l < 1 {
        return 
    }
    dp := make([][]int, l)
    for i, arr := range grid {
        dp[i] = make([]int, len(arr))
    }
    dp[][] = grid[][]
    for i := ; i < l; i++ {
        for j := ; j < len(grid[i]); j++ {
            if i ==  && j !=  {
                dp[i][j] = dp[i][j-1] + grid[i][j]
            } else if j ==  && i !=  {
                dp[i][j] = dp[i-1][j] + grid[i][j]
            } else if i !=  && j !=  {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
            }
        }
    }
    return dp[l-1][len(dp[l-1])-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

同样，运行上面的代码，我们发现使用的内存过大。有没有什么办法可以压缩内存呢？通过观察我们发现，在我们自左上角到右下角计算分区的小路径和的过程中，我们只需要使用到之前已经累积计算完毕的数据，并且不会再次访问之前的元素数据。重新成图如下：(大家看这个过程像不像扫雷，其实如果大家研究扫雷外挂的话，就会发现在扫雷的核心算法中，就有一处颇为类似这种分析方法，这里就不深究了）

优化后的代码如下：

func minPathSum(grid [][]int) int {
    l := len(grid)
    if l < 1 {
        return 
    }
    for i := ; i < l; i++ {
        for j := ; j < len(grid[i]); j++ {
            if i ==  && j !=  {
                grid[i][j] = grid[i][j-1] + grid[i][j]
            } else if j ==  && i !=  {
                grid[i][j] = grid[i-1][j] + grid[i][j]
            } else if i !=  && j !=  {
                grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
            }
        }
    }
    return grid[l-1][len(grid[l-1])-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过go。算法思想重要，使用go纯属作者爱好。

记者于公众号-浩仔讲算法