公司网站栏目,wordpress博文图片,项目四网站建设实训报告,企业做淘宝客网站[动态规划] (九) 路径问题#xff1a;LeetCode 64.最小路径和 文章目录 [动态规划] (九) 路径问题#xff1a;LeetCode 64.最小路径和题目解析解题思路状态表示状态转移方程初始化和填表顺序返回值 代码实现总结 64. 最小路径和 题目解析
(1) 从左上角到右下角
(2) 只能向右…[动态规划] (九) 路径问题LeetCode 64.最小路径和 文章目录 [动态规划] (九) 路径问题LeetCode 64.最小路径和题目解析解题思路状态表示状态转移方程初始化和填表顺序返回值 代码实现总结 64. 最小路径和 题目解析
(1) 从左上角到右下角
(2) 只能向右或者向下移动’
(3) 使路径上数字最小
解题思路
路径问题我们已经做过很多了可以总结出一些经验。
我们先按照经验来做不成功就换另一种经验。
状态表示
dp[i] [j]以(ij)为终点(或者起点哪种简单且能做出题用哪种)所得的路径和。
状态转移方程
dp(ij)的路径和取决于上一个位置(dp[i-1] [j])和左一个位置(dp[i] [j-1])的较小值。
当然还要加上(ij)当前位置的值。
所以
dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]初始化和填表顺序
初始化
和以往一样为了方便填表我们多开辟一列和一行。
我们是访问i-1、j-1的位置一般也就初始化左上角周围的位置。
由于1号位置受到2号和3号的影响为了不影响结果我们赋值为0让它只取原表的当前位置即可。 而4、5、6、7、8号位置避免影响结果初始化为整型最大值即可因为当初始化为0时就会取这些位置的0而不是dp数组中的值。
填表顺序
一列一列填即可。
返回值
我们扩大一列和一行返回(mn)位置的值即可。
dp[m] [n]
看到这里就可以去尝试实现代码了之后再来看下面的内容。 代码实现
class Solution {
public:int minPathSum(vectorvectorint grid) {//创建dp数组int m grid.size(), n grid[0].size();vectorvectorint dp(m1, vectorint(n1, INT_MAX));//初始化dp[1][0] dp[0][1] 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];}
};总结
细节1方便初始化我们将dp数组中的值都定义为INT_MAX再把需要的位置初始化为0即可。
细节2扩大了一列和一行下标对应到原表(grid)时就需要调整为(i-1j-1)。 细节3一般最小和问题都需要注意初始化时记得把不相干位置初始化为整数最大值。
