Leetcode64. 最小路径和

题目描述

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

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

示例 1：

img

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

示例 2：

1
2
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

解题思路

这道题是经典的动态规划题。

由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。

对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。

创建一个二维数组dpdp，dp[i][j]dp[i][j]表示从左上角出发到（i,j）（i,j）位置的最小路径和。显然，有以下公式：

\begin{eqnarray} && 其实条件：dp[i][j]=grid[0][0]; \\\\ && 当i>0且j=0时,\quad dp[i][0]=dp[i-1][0]+grid[i][0]; \\\\ && 当i=0且j>0时,\quad dp[0][j]=dp[0][j-1]+grid[0][j]; \\\\ && 当i>0且j>0时,\quad dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]; \end{eqnarray}

最后得到的dp[rowNum−1][colNum−1]dp[rowNum-1][colNum-1]即为所求。

具体细节如示例代码所示：

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int minPathSum(vector<vector<int>>& grid)
{
    int rowNum = grid.size();       //行数
    int colNum = grid[0].size();    //列数
    vector<vector<int>> dp(rowNum,vector<int>(colNum,0));
    dp[0][0]=grid[0][0];
    for(int i=1;i<colNum;++i)
    {
        dp[0][i]=dp[0][i-1]+grid[0][i];
    }
    for(int i=1;i<rowNum;++i)
    {
        dp[i][0]=dp[i-1][0]+grid[i][0];
    }
    for(int row=1;row<rowNum;++row)
    {
        for(int col=1;col<colNum;++col)
        {
            //从上边或左边耗费更小的一格走到当前
            dp[row][col]=min(dp[row-1][col],dp[row][col-1])
                            +grid[row][col];
        }
    }
    return dp[rowNum-1][colNum-1];
}

时间复杂度：O(mn)O(mn)，其中$ m $和 nn 分别是网格的行数和列数。

空间复杂度：O(mn)O(mn)，其中$ m $和 nn 分别是网格的行数和列数。

空间复杂度可以通过滚动数组优化到O(n)O(n)!