(力扣---动态规划)最小路径和_最小路径和动态规划四方向

作者：花生_TL007 | 2024-06-12 22:06:48

踩

最小路径和动态规划四方向

(力扣—动态规划)最小路径和

问题描述：

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

说明：

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

思想：

这是一道非常常规且基础的动态规划的题目，非常适合自己去理解dp的解题思路。
本解采用最基础的解法。

dp方程：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
解释：
其实很简单，题目说了只能向右或者向下走一步，所以当前步骤的最小路径和就是上一步(从上方向下方走，或从左方向右方走)的最小路径和加上当前步骤的grid权值。所以就需要初始化第0行与第0列为本行或本列当前位置和。

代码

    int minPathSum(vector<vector<int>>& grid) {
   
        vector<vector<int>> dp(grid.size(), vector<int>(grid[01
2

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/709828

(力扣---动态规划)最小路径和_最小路径和 动态规划 四方向

(力扣—动态规划)最小路径和

问题描述：

说明：

思想：

代码

(力扣---动态规划)最小路径和_最小路径和动态规划四方向