【AICon】 如何构建高效的 RAG 系统?RAG 技术在实际应用中遇到的挑战及应对策略?>>> 了解详情
写点什么

图解算法——动态规划系列

  • 2020-03-26
  • 本文字数:7493 字

    阅读完需:约 25 分钟

图解算法——动态规划系列

动态规划系列一:爬楼梯

1.1 概念讲解

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


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



图 1


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


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 阶

  • 2 阶

  • 示例 2

  • 输入:3 输出:3 解释:有三种方法可以爬到楼顶。

  • 1 阶 + 1 阶 + 1 阶

  • 1 阶 + 2 阶

  • 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) 阶的方法数之和。



图 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],那么 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]



图 3

2.3 Go 语言示例

根据分析,得到代码如下:


func maxSubArray(nums []int) int {    if len(nums) < 1 {        return 0    }    dp := make([]int, len(nums))    //设置初始化值     dp[0] = nums[0]    for i := 1; i < len(nums); i++ {        //处理 dp[i-1] < 0 的情况        if dp[i-1] < 0 {            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 0    }    dp := make([]int, len(nums))    result := nums[0]    dp[0] = nums[0]    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 题目图解

首先我们分析题目,要找的是最长上升子序列(Longest Increasing Subsequence,LIS)。因为题目中没有要求连续,所以 LIS 可能是连续的,也可能是非连续的。同时,LIS 符合可以从其子问题的最优解来进行构建的条件。所以我们可以尝试用动态规划来进行求解。首先我们定义状态:


dp[i] :表示以 nums[i]结尾的最长上升子序列的长度


我们假定 nums 为[1,9,5,9,3]



图 4


我们分两种情况进行讨论:


  • 如果 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 数组中的最大值,就是我们要找的答案。


分析完毕,我们绘制成图:



图 5

3.3 Go 语言示例

根据分析,得到代码如下:


func lengthOfLIS(nums []int) int {    if len(nums) < 1 {        return 0    }    dp := make([]int, len(nums))    result := 1    for i := 0; i < len(nums); i++ {        dp[i] = 1        for j := 0; 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]]



图 6


那从上到下的最小路径和就是 2-3-5-1,等于 11。


由于我们是使用数组来定义一个三角形,所以便于我们分析,我们将三角形稍微进行改动:



图 7


这样相当于我们将整个三角形进行了拉伸。这时候,我们根据题目中给出的条件:每一步只能移动到下一行中相邻的结点上。其实也就等同于,每一步我们只能往下移动一格或者右下移动一格。将其转化成代码,假如 2 所在的元素位置为[0,0],那我们往下移动就只能移动到[1,0]或者[1,1]的位置上。假如 5 所在的位置为[2,1],同样也只能移动到[3,1]和[3,2]的位置上。如下图所示:



图 8


题目明确了之后,现在我们开始进行分析。题目很明显是一个找最优解的问题,并且可以从子问题的最优解进行构建。所以我们通过动态规划进行求解。首先,我们定义状态:


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


我们很容易想到可以自顶向下进行分析。并且,无论最后的路径是哪一条,它一定要经过最顶上的元素,即[0,0]。所以我们需要对 dp[0][0]进行初始化。


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


继续分析,如果我们要求 dp[i][j],那么其一定会从自己头顶上的两个元素移动而来。



图 9


如 5 这个位置的最小路径和,要么是从 2-3-5 而来,要么是从 2-4-5 而来。然后取两条路径和中较小的一个即可。进而我们得到状态转移方程:


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


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



图 10


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



图 11


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


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



图 12


我们可以直接将其特殊处理,得到:


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 步:


  • 定义状态

  • 总结状态转移方程

  • 分析状态转移方程不能满足的特殊情况。

  • 得到最终解

4.3 代码分析

分析完毕,代码自成:


func minimumTotal(triangle [][]int) int {    if len(triangle) < 1 {        return 0    }    if len(triangle) == 1 {        return triangle[0][0]    }    dp := make([][]int, len(triangle))    for i, arr := range triangle {        dp[i] = make([]int, len(arr))    }    result := 1<<31 - 1    dp[0][0] = triangle[0][0]    dp[1][1] = triangle[1][1] + triangle[0][0]    dp[1][0] = triangle[1][0] + triangle[0][0]    for i := 2; i < len(triangle); i++ {        for j := 0; j < len(triangle[i]); j++ {            if j == 0 {                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}
复制代码



图 13


运行上面的代码,我们发现使用的内存过大。我们有没有什么办法可以压缩内存呢?通过观察我们发现,在我们自顶向下的过程中,其实我们只需要使用到上一层中已经累积计算完毕的数据,并且不会再次访问之前的元素数据*绘制成图如下:



图 14


优化后的代码如下:


func minimumTotal(triangle [][]int) int {    l := len(triangle)    if l < 1 {        return 0    }    if l == 1 {        return triangle[0][0]    }    result := 1<<31 - 1    triangle[0][0] = triangle[0][0]    triangle[1][1] = triangle[1][1] + triangle[0][0]    triangle[1][0] = triangle[1][0] + triangle[0][0]    for i := 2; i < l; i++ {        for j := 0; j < len(triangle[i]); j++ {            if j == 0 {                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}
复制代码



图 15

动态规划系列五:最小路径和

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

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]]



图 16


那从左上角到右下角的最小路径和,我们可以很容易看出就是 1-3-1-1-1,这一条路径,结果等于 7。


题目明确了,我们继续进行分析。该题与上一道求三角形最小路径和一样,题目明显符合可以从子问题的最优解进行构建,所以我们考虑使用动态规划进行求解。首先,我们定义状态:


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


同样,因为任何一条到达右下角的路径,都会经过[0,0]这个元素。所以我们需要对 dp[0][0]进行初始化。


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


继续分析,根据题目给的条件,如果我们要求 dp[i][j],那么它一定是从自己的上方或者左边移动而来。如下图所示:



图 17


  • 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)



图 18


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


设: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 0    }    dp := make([][]int, l)    for i, arr := range grid {        dp[i] = make([]int, len(arr))    }    dp[0][0] = grid[0][0]    for i := 0; i < l; i++ {        for j := 0; j < len(grid[i]); j++ {            if i == 0 && j != 0 {                dp[i][j] = dp[i][j-1] + grid[i][j]            } else if j == 0 && i != 0 {                dp[i][j] = dp[i-1][j] + grid[i][j]            } else if i != 0 && j != 0 {                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}
复制代码



图 19


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



图 20


优化后的代码如下:


func minPathSum(grid [][]int) int {    l := len(grid)    if l < 1 {        return 0    }    for i := 0; i < l; i++ {        for j := 0; j < len(grid[i]); j++ {            if i == 0 && j != 0 {                grid[i][j] = grid[i][j-1] + grid[i][j]            } else if j == 0 && i != 0 {                grid[i][j] = grid[i-1][j] + grid[i][j]            } else if i != 0 && j != 0 {                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}
复制代码



图 21


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

原文首发于公众号-浩仔讲算法


2020-03-26 18:592192

评论 1 条评论

发布
用户头像
通俗易懂
2021-07-23 18:11
回复
没有更多了
发现更多内容

Hive对分区分桶表的操作

五分钟学大数据

大数据 hive 5月日更

绍兴柯桥学历提升培训到哪里?兴德

Geek_196d9f

绍兴柯桥JAVA,web前端编程培训到哪里?兴德

Geek_196d9f

绍兴柯桥3Dmax效果图培训到哪里?兴德

Geek_196d9f

一颗CPU与病魔赛跑

E科讯

并发王者课 - 青铜4:synchronized用法初体验

MetaThoughts

Java 多线程 并发 并发王者课

绍兴柯桥CAD制图培训到哪里?兴德!

Geek_196d9f

人生算法:内控控制点

石云升

读书笔记 思维模型 5月日更

最详细的 Python 结合 RFM 模型实现用户分层实操案例!

JackTian

Python 编程 程序员 数据分析 RFM模型

KubeSphere+QKE 轻松实现容器多集群管理

青云技术社区

容器 k8s 开发工具

绍兴柯桥淘宝拼多多电商培训到哪里?兴德

Geek_196d9f

绍兴柯桥室内设计培训到哪里?兴德

Geek_196d9f

绍兴柯桥平面设计培训到哪里?兴德

Geek_196d9f

绍兴柯桥数码印花金昌描稿调色分色培训到哪里?兴德

Geek_196d9f

绍兴柯桥电脑办公培训到哪里?兴德

Geek_196d9f

绍兴柯桥插花花艺培训到哪里?兴德

Geek_196d9f

智能量化网格策略交易机器人,马丁倍投机器人

千万级学生管理系统考试试卷存储方案

chenmin

支持多套对象存储,冷热数据分层又添新功能

焱融科技

分布式 云原生 高性能 文件存储 技术博客

绍兴柯桥摄影摄像培训到哪里?兴德!

Geek_196d9f

Leveldb解析之五:理解leveldb的持久化和MVCC实现机制

Jowin

leveldb

低代码核心优势是:降本增效+多系统集成,这真的对吗?

优秀

低代码

五种网络IO模型详解

Linux服务器开发

后端 epoll Linux服务器开发 网络io 网络模型

绍兴柯桥PS培训到哪里?怎么修图?兴德

Geek_196d9f

绍兴柯桥会计实操培训到哪里?兴德

Geek_196d9f

绍兴柯桥淘宝美工培训到哪里?兴德

Geek_196d9f

IDC数据中心介绍

大数据技术指南

数据中心 5月日更

聊聊业务数据分析那些事儿

小飞象@木木自由

数据分析 业务场景分析 业务数据分析 业务分析

Kubernetes 稳定性保障手册:洞察+预案

阿里巴巴云原生

数据库 容器 云原生 k8s 监控

绍兴柯桥服装设计培训到哪里?兴德

Geek_196d9f

绍兴柯桥视频剪辑影视后期PR,AE培训到哪里?兴德

Geek_196d9f

图解算法——动态规划系列_文化 & 方法_小浩_InfoQ精选文章