最小路径和[中等]

优质博文：IT-BLOG-CN

一、题目

给定一个包含非负整数的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.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

二、代码

动态规划

状态定义：设 dp 为大小 m×n 矩阵，其中 dp[i][j] 的值代表直到走到 (i,j) 的最小路径和。

转移方程：题目要求，只能向右或向下走，换句话说，当前单元格 (i,j) 只能从左方单元格 (i−1,j) 或上方单元格 (i,j−1) 走到，因此只需要考虑矩阵左边界和上边界。

走到当前单元格 (i,j) 的最小路径和 = “从左方单元格 (i−1,j) 与 从上方单元格 (i,j−1) 走来的 两个最小路径和中较小的 ” + 当前单元格值 grid[i][j] 。具体分为以下 4 种情况：
当左边和上边都不是矩阵边界时： 即当i!=0, j!=0时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j] ；
当只有左边是矩阵边界时： 只能从上面来，即当i=0,j!=0时， dp[i][j]=dp[i][j−1]+grid[i][j] ；
当只有上边是矩阵边界时： 只能从左面来，即当i!=0,j=0时， dp[i][j]=dp[i−1][j]+grid[i][j] ；
当左边和上边都是矩阵边界时： 即当i=0,j=0时，其实就是起点， dp[i][j]=grid[i][j]；

初始状态：dp 初始化即可，不需要修改初始 0 值。

返回值：返回 dp 矩阵右下角值，即走到终点的最小路径和。
其实我们完全不需要建立 dp 矩阵浪费额外空间，直接遍历 grid[i][j] 修改即可。这是因为：grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] ；原 grid 矩阵元素中被覆盖为 dp 元素后（都处于当前遍历点的左上方），不会再被使用到。

class Solution {public int minPathSum(int[][] grid) {for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(i == 0 && j == 0) continue;else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];}}return grid[grid.length - 1][grid[0].length - 1];}
}

时间复杂度 O(M×N) 遍历整个grid矩阵元素。
空间复杂度 O(1) 直接修改原矩阵，不使用额外空间。

空间复杂度可以优化到原地工作，也就是O1，但是会破坏原矩阵的数据。通过分析可以发现，数据在扫描矩阵的时候，原数据信息只在扫描的时候用到一次，后续便不会再使用，所以扫描写dp的时候，可以直接进行覆盖，而不会影响最终的结局。也就是利用了系统为grid分配的内存进行记录动态规划的dp。下面贴上代码（代码写的烂，如果有人读到了，还请见谅）

#define min(x,y) ((x) > (y)) ? (y) : (x)int minPathSum(int** grid, int gridSize, int* gridColSize){unsigned char i,j;for(j = 1; j < *gridColSize;j++)      grid[0][j] += grid[0][j-1];for(i = 1; i < gridSize;i++)          grid[i][0] += grid[i-1][0];for(i = 1; i < gridSize; i++)for(j = 1; j < *gridColSize;j++ ) grid[i][j] += min(grid[i-1][j],grid[i][j-1]);return grid[gridSize-1][*gridColSize-1];
}