【LeetCode热题100】【多维动态规划】最小路径和

叶茂林

发布于 2024-04-24 08:15:43

1020

发布于 2024-04-24 08:15:43

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目链接：64. 最小路径和 - 力扣（LeetCode）

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

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

经典动态规划问题，到达当前格子的路径和要么是加上从上面格子来的，要么是加上左边格子来的，取这两个方向来的较小者就行了

对于最左边的和最上边的没有两个方向，可以直接累加一个方向的

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 1; i < n; ++i)
            grid[0][i] += grid[0][i - 1];
        for (int i = 1; i < m; ++i)
            grid[i][0] += grid[i - 1][0];
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
        return grid[m - 1][n - 1];
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-23，如有侵权请联系 cloudcommunity@tencent.com 删除

grid