leetcode 64 最小路径和

描述：

题目给个矩阵，每个点有个权重，左上到右下，只能往右或下走，求最小路径。

解决：

dp[i][j] = min(d[i -1][j], dp[i][j - 1]) + dp[i][j]

更新一遍即可，改为一维。

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

注意，在原数组的基础上改不是很好，自己定义个数组存就可以了。

leetcode 64 最小路径和

推荐阅读