《剑指offer》第29天：m x n 网格的最小路径和

程序员小浩

发布于 2020-09-22 10:20:58

6770

发布于 2020-09-22 10:20:58

文章被收录于专栏：小浩算法

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

01、题目分析

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

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

示例:

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

这道题有一定难度哦！如果没有思路请回顾上一篇的学习内容！ 不建议直接看题解！

02、题目图解

首先我们分析题目，要找的是 最小路径和， 这是个啥意思呢？假设我们有一个 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 步：

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

03、GO语言示例

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

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
}

运行结果：

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

优化后的代码如下：

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
}

运行结果：

java：

class Solution {
    public int minPathSum(int[][] grid) {
        int l = grid.length;
        if (l < 1) {
            return 0;
        }
        for(int i = 0; i < l; i++)  {
            for(int j = 0; j < grid[i].length; 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) {
                    grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
                }
            }
        }
        return grid[l-1][grid[l-1].length - 1];
    }
    
    
    public int min(int a, int b) {
        return a > b ? b : a;
    }

}

运行结果：