面试刷题-动态规划-求解最短路径

题目链接

https://leetcode-cn.com/problems/minimum-path-sum/

题目描述

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

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

示例 1：

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

示例 2：

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

题目分析

这是一个典型的动态规划的题目。每个元素对应的最小路径与其相邻元素对应的最小路径有关。

具体实现上，创建二维数组 $\textit{dp}$，与原始网格的大小相同，$\textit{dp}[i][j]$表示从左上角出发到(i,j)位置的最小路径和。显然，$\textit{dp}[0][0]=\textit{grid}[0][0]$。对于$\textit{dp}$中的其余元素，通过以下状态转移方程计算元素值。

当i>0且j=0时，$\textit{dp}[i][0]=\textit{dp}[i-1][0]+\textit{grid}[i][0]$。

当i=0且j>0时，$\textit{dp}[0][j]=\textit{dp}[0][j-1]+\textit{grid}[0][j]$。

当i>0且j>0时，$\textit{dp}[i][j]=\min(\textit{dp}[i-1][j],\textit{dp}[i][j-1])+\textit{grid}[i][j]$。

最后得到$\textit{dp}[m-1][n-1]$的值即为从网格左上角到网格右下角的最小路径和。

实现代码

我实现的代码：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }

        std::vector<std::vector<int> > sum(row, std::vector<int>(col, 0));

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (i == 0 && j == 0) {
                    sum[i][j] = grid[i][j];
                } else if (i == 0 && j > 0) {
                    sum[i][j] = sum[i][j - 1] + grid[i][j];
                } else if (i > 0 && j == 0) {
                    sum[i][j] = sum[i - 1][j] + grid[i][j];
                } else {
                    sum[i][j] = std::min(sum[i][j - 1] + grid[i][j], sum[i - 1][j] + grid[i][j]);
                }
            }
        }
        return sum[row - 1][col - 1];
    }
};

官方实现的代码：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }

        int rows = grid.size(), columns = grid[0].size();
        auto dp = vector < vector <int> > (rows, vector <int> (columns));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
};

复杂度分析

时间复杂度：O(mn)，其中m和 n分别是网格的行数和列数。需要对整个网格遍历一次，计算dp的每个元素的值。

空间复杂度：O(mn)，其中m和n分别是网格的行数和列数。创建一个二维数组 dp和网格大小相同。

空间复杂度可以优化，例如每次只存储上一行的dp值，则可以将空间复杂度优化到 O(n)。

优化空间复杂度到O(n)的代码实现:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }

        int rows = grid.size();
        int columns = grid[0].size();
        auto dp = vector<int>(columns);

        dp[0] = grid[0][0];
        for (int i = 1; i < columns; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }

        for (int j = 1; j < rows; j++) {
            dp[0] = dp[0] + grid[j][0];
            for (int k = 1; k < columns; k++) {
                dp[k] = std::min(dp[k] + grid[j][k], dp[k - 1] + grid[j][k]);
            }
        }

        return dp[columns - 1];
    }
};

除非注明，否则均为[半杯茶的小酒杯]原创文章，转载必须以链接形式标明本文链接

本文链接： http://www.banbeichadexiaojiubei.com/index.php/2020/12/26/%e9%9d%a2%e8%af%95%e5%88%b7%e9%a2%98-%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92-%e6%b1%82%e8%a7%a3%e6%9c%80%e7%9f%ad%e8%b7%af%e5%be%84/