都匀网站开发,建设工程信息网官网首页,嘉兴做网站优化多少钱,阿里巴巴电脑版网页文章目录 前言一、题目分析二、算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值是什么 三、代码实现总结 前言
在本文章中#xff0c;我们将要详细介绍一下Leetcode6最小路径相关的内容
一、题目分析 二、算法原理
1.状态表示
列出dp表#xff0c;dp[i][j]代… 文章目录 前言一、题目分析二、算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值是什么 三、代码实现总结 前言
在本文章中我们将要详细介绍一下Leetcode6最小路径相关的内容
一、题目分析 二、算法原理
1.状态表示
列出dp表dp[i][j]代表到达该位置数字之和最小
2.状态转移方程
根据最近一步划分问题 1.dp[i][j]从上面位置再往下走一步到达该位置这个上边位置就是dp[i-1][j] 2.dp[i][j]从左面位置再往右走一步到达该位置这个上边位置就是dp[i][j-1] 3.二者最小值再加上当前位置的值就是dp[i][j]
dp[i][j]min(dp[i-1][j],dp[i][j-1])gr[i][j];
3.初始化
a.下标的映射关系 b.虚拟位置的值保证后面填表正确 c.注意开头位置的初始化不要越界 dp[0][1]和dp[1][0]位置要初始化为0 其余虚拟位置初始化为INT_MAX; 注意图中的三个位置
4.填表顺序
从上到下从左到右
5.返回值是什么
dp[m][n]
三、代码实现
class Solution {
public:int minPathSum(vectorvectorint gr) {//建表int mgr.size();int ngr[0].size();int dp[m1][n1];//初始化for(int i0;im;i){for(int j0;jn;j){dp[i][j]INT_MAX;}}dp[0][1]dp[1][0]0;//填表for(int i1;im;i){for(int j1;jn;j){dp[i][j]min(dp[i-1][j],dp[i][j-1])gr[i-1][j-1];}}//返回值return dp[m][n];}
};总结
以上就是我们对Leetcode—64. 最小路径和(Leetcode)详细介绍希望对大家的学习有所帮助仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~
