LeetCode刷题--- 最小路径和
2024-01-10 11:24:35
个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
【C++】? ??
??????http://t.csdnimg.cn/6AbpV
数据结构与算法
前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的 ?
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
最小路径和
题目链接:最小路径和
题目
给定一个包含非负整数的?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
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
解法
题目解析
- 给定一个包含非负整数的?
m?x?n
?网格?grid
?。 - 找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
- 每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。
算法原理讲解
我们这题使用动态规划,我们做这类题目可以分为以下五个步骤
- 状态显示
- 状态转移方程
- 初始化(防止填表时不越界)
- 填表顺序
- 返回值
- 状态显示
dp[i][j]
表?:到达
[i, j]
位置处,最?路径和是多少。
- 状态转移方程
如果dp[i][j] 表?到达 到达 [i, j] 位置处的最?路径和,那么到达 [i, j] 位置之前的??步,有两种情况:
- 从 [i - 1, j] 向下??步,转移到 [i, j] 位置;
- 从 [i, j - 1] 向右??步,转移到 [i, j] 位置。
由于到
[i, j]
位置两种情况,并且我们要找的是最?路径,因此只需要这两种情况下的最?值,再加上 [i, j]
位置上本?的值即可。也就是: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i-1][j-1]
- 初始化(防止填表时不越界)
可以在最前?加上?个「辅助结点」,帮助我们初始化。使?这种技巧要注意两个点
- 辅助结点??的值要「保证后续填表是正确的」;
- 「下标的映射关系」。
「添加??」,并且「添加?列」后,所有位置的值可以初始化为?穷?,然后让 dp[0][1] = dp[1][0] = 0?即可。
- 填表顺序
根据「状态转移?程」的推导来看,填表的顺序就是「从上往下」填每??,每??「从左往 后」。
- 返回值
根据「状态表?」,我们要返回的结果是
dp[m][n]。
代码实现
- 时间复杂度:O(mn),其中 m?和 n?分别是网格的行数和列数。需要对整个网格遍历一次,计算 dp 的每个元素的值。
- 空间复杂度:O(mn),其中 m?和 n 分别是网格的行数和列数。创建一个二维数组 dp,和网格大小相同。
- 空间复杂度可以优化,例如每次只存储上一行的 dp 值,则可以将空间复杂度优化到 O(n)。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid)
{
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
dp[0][1] = dp[1][0] = 0; // 初始化
// 填表
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]) + grid[i-1][j-1];
}
}
return dp[m][n];
}
};
文章来源:https://blog.csdn.net/weixin_74268082/article/details/135494810
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!