64.最小路径和

64.最小路径和一、题目

1.题目描述2.基础框架3.解题思路

原题链接：64.最小路径和

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

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

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100 2.基础框架

C++基础框架代码如下:

int minPathSum(vector>& grid){
}

题目分析

题目目标返回从左上角向右下角的最小路径和，属于最小值问题。

每次移动的方向只能向右或向下。

当i = 0时，只有一条路径，(0,j)结点应该初始化为到的该结点的最小路径和。

当j = 0时，也只有一条路径，(i，0)结点应该初始化为到该结点的最小路径和。

其余情况的(i,j)结点可以从上面或左边转移过来，那走到(i,j)结点的最小路径和为min{上方的最小路径和，左方的最小路径和} + (i,j)结点的值。

可以看出存在递推的过程，那么采用动态规划，定义dp[i][j]数组，含义为到达(i,j)结点的最小路径和。

递推公式（状态转移方程）：

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

从递推公式来看，我们需要初始化dp[i][j]当i = 0和当j = 0的情况。

由于递推的过程不影响后面递推的逻辑，所以这里的动态规划操作可以在原数组上进行操作。

实现代码：

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