制作网页和网站有啥不同,安装文件出现乱码,wordpress主题翻译插件,电脑课程培训零基础优质博文#xff1a;IT-BLOG-CN
一、题目
给定一个包含非负整数的m x n网格grid#xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。
说明#xff1a;每次只能向下或者向右移动一步。
示例 1#xff1a;
输入#xff1a;grid [[…优质博文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] 当只有左边是矩阵边界时 只能从上面来即当i0,j!0时 dp[i][j]dp[i][j−1]grid[i][j] 当只有上边是矩阵边界时 只能从左面来即当i!0,j0时 dp[i][j]dp[i−1][j]grid[i][j] 当左边和上边都是矩阵边界时 即当i0,j0时其实就是起点 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];
}
