LeetCode:最小路径和

64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思路：

一个结点只能往右或者往下走，那么该结点到右下角的最短路径等于其本身加上 该结点右面结点到右下角的最短路径 与 该结点下面结点到右下角的最短路径。
边界条件：

• 当前结点为右下角结点时，返回右下角结点的值
• 最后一行的结点只能往右走，该结点的最短路径等于该结点右面结点到右下角的最短路径
• 最后一列的结点只能往下走，该结点的最短路径等于该结点下面结点到右下角的最短路径

递归代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0)
            return 0;
        return help(grid, 0, 0);
    }

    int help(vector<vector<int>>& grid, int i, int j)
    {
        if (i == grid.size() - 1 && j == grid[0].size() - 1)
            return grid[i][j];
        if (i == grid.size() - 1)
            return grid[i][j] + help(grid, i, j + 1);
        if (j == grid[0].size() - 1)
            return grid[i][j] + help(grid, i + 1, j);
        int right = help(grid, i, j + 1);
        int down = help(grid, i + 1, j);
        return grid[i][j] + (right<down ? right : down);
    }
};

动态规划代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0)
            return 0;
        int row = grid.size() - 1, col = grid[0].size() - 1;
        for (int i = col - 1; i >= 0; --i)  //初始化最后一行
        {
            grid[row][i] = grid[row][i] + grid[row][i + 1];
        }
        for (int i = row - 1; i >= 0; --i)  //初始化最后一列
        {
            grid[i][col] = grid[i][col] + grid[i + 1][col];
        }
        for (int i = row - 1; i >= 0; --i)  //一般元素
        { 
            for (int j = col - 1; j >= 0; --j)
            {
                grid[i][j] = grid[i][j] + (grid[i + 1][j]<grid[i][j + 1] ? grid[i + 1][j] : grid[i][j + 1]);
            }
        }
        return grid[0][0];
    }
};