牛客热题：矩阵的最小路径和

📟作者主页：慢热的陕西人
🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：矩阵的最小路径和

题目链接

矩阵的最小路径和_牛客题霸_牛客网 (nowcoder.com)

方法一：二维dp

思路

①状态表示：

​ $dp[i][j]$ 表示为从起点(0, 0)到(i, j)位置的最小路径和

②初始化：

​ 首先对于第一行第一列来说，他们的路径都只有一条，就是从他们的上方或者左方到达，因此我们可以直接计算出他们的路径和。

③状态转移方程：

​ 对于每一个位置来说，有两个路径来源，我们选取路径和小的就可以。

​ $dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]$

④填表顺序：

​ 我们发现当前位置状态的获取都需要依赖上方和左方位置的状态，因此我们填表顺序为：

从上到下，从左到右。

⑤返回结果：

​ 因为答案要求的是从起点到终点的最小路径和，因此我们要返回的结果就是$dp[m-1][n-1]$

代码

int minPathSum(vector<vector<int> >& matrix) {int m = matrix.size();int n = matrix[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));//初始化dp[0][0] = matrix[0][0];for(int i = 1; i < m || i < n; ++i){if(i < m) dp[i][0] = dp[i - 1][0] + matrix[i][0];if(i < n) dp[0][i] = dp[0][i - 1] + matrix[0][i];}for(int i = 1; i < m; ++i)for(int j = 1; j < n; ++j){dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];}return dp[m - 1][n - 1];}

复杂度

时间复杂度：遍历了一次二维dp数组：$O(m\ast n)$

空间复杂度：使用了额外的二维数组：$O(m\ast n)$