DP 第五讲 - 最小路径和

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

01、题目分析

第64题:最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

  1. 输入:
  2. [
  3. [1,3,1],
  4. [1,5,1],
  5. [4,2,1]
  6. ]
  7. 输出: 7
  8. 解释: 因为路径 13111 的总和最小。


这道题有一定难度哦!如果没有思路请回顾上一篇的学习内容!

不建议直接看题解!

02、题目图解

首先我们分析题目,要找的是 最小路径和,这是个啥意思呢?假设我们有一个 m * n 的矩形 :[[1,3,1],[1,5,1],[4,2,1]]

PNG

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


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

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

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

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

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

PNG

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)

PNG

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

设:dp的长度为l
最终结果就是:dp[l-1][len(dp[l-1])-1]

综上我们就分析完了,我们总共进行了 4 步:

  1. 定义状态
  2. 总结状态转移方程
  3. 分析状态转移方程不能满足的特殊情况。
  4. 得到最终解

03、GO语言示例

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

  1. func 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. func min(a, b int) int {
  25. if a > b {
  26. return b
  27. }
  28. return a
  29. }

运行结果:

PNG

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

PNG

优化后的代码如下:

  1. func 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. func min(a, b int) int {
  20. if a > b {
  21. return b
  22. }
  23. return a
  24. }

运行结果:

PNG


课后思考:路径和类问题和之前的子序列类问题有何区别?