力扣解题思路：最小路径和问题 |
您所在的位置：网站首页 › python抠图只能抠正方形吗 › 力扣解题思路：最小路径和问题 |
|
64. 最小路径和
思路：题目：
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。其中，次只能向下或者向右移动一步。
显然每一步的路径总和都与上一步有关，那么我们马上能想到使用动态规划解题，首先找到动态方程：
dp[i][j] = Math.min(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1])
然后就可以愉快的写代码了： public int minPathSum(int[][] grid) { int[][] dp = new int[grid.length+1][grid[0].length+1]; for(int i=1;i dp[i][j] = Math.min(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]); } } return dp[grid.length][grid[0].length]; }然后我就在两分钟内写完了，写完一看，不对劲呀，为什么我比所有人的代码都短？？于是我运行了一下。。。果然错了/(ㄒoㄒ)/~~ 我天真的以为我把动态规划的数组的上侧和左侧填充一下就可以避免手动的去设置初始值，后来发现错了，按照我的这种做法，其实整个grid数组的第一行和第一列都可以作为出发点，然而题目要求只能从grid[0][0]出发，我这种方法相当于只初始化了第一行的第一列，所以出现了问题（dp数组的第一行和第一列被错误的初始化成grid的第0行和第0列了），所以我就老老实实的重新定义dp数组了： int[][] dp = new int[grid.length][grid[0].length];这样一看，dp数组的维度和grid数组一样，完全可以用grid数组代替dp数组啊，还能节省空间，于是我在for循环中重新定义了一下边界和动态规划数组的更新方式： public int minPathSum(int[][] grid) { for (int row = 0; row if (row == 0 && col == 0) { continue; } else if (row == 0) { grid[row][col] += grid[row][col - 1]; } else if (col == 0) { grid[row][col] += grid[row - 1][col]; } else { grid[row][col] += Math.min(grid[row][col - 1], grid[row - 1][col]); } } } return grid[grid.length - 1][grid[0].length - 1]; }按照二维动态规划数组的思路，其实也可以用一维动态规划数组，数组更新的方式是类似的，此时动态规划数组是按列更新的： public int minPathSum(int[][] grid) { if (grid.length == 0 || grid[0].length == 0) { return 0; } int m = grid |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |