动态规划--最小路径和
题目:
64. 最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思路:
可以向下或者向右,2种可能性,可以联想到状态转移方程是根据这个来的。首先 用基本思路,2维数组来表示 到达每一步的最小路径和。比如我们从 左上角开始走。因为他只能向下或者向右,所以 第一行和第一列其实是可以直接计算的,只要累加求和即可
难点就在于非第一行和第一列的:
比如走到5的时候。可能是3 向下 或者是 2 向右。 明显 2向右 成本更低 故 5的位置 为 (5+2)。
状态转移方程为:dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1])
代码 如下
public int getMin(int[][] grid) {
// 初始化dp数组,尺寸和原数组一致
int[][] dp = new int[grid.length][grid[0].length];
dp[0][0] = grid[0][0];
// 初始化第一行
for(int i = 1; i < grid.length;i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
// 初始化第一列
for(int j = 1; j < grid.length;j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
// 填充其他位置的元素
for(int i = 0; i < grid.length;i++) {
for(int j = 0; j < grid[0].length;j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i]dp[j-1]);
}
}
return dp[grid.length][grid[0];
}
压缩空间解法
如果不用二维数组,使用一维数组其实也可以。就是不断复用上一次的数组。
这道题 从左上 或者从右下 其实都可以。从左上 就是返回右下 的值,相反亦是
比如从左上开始,第一步,初始化第一行,因为就一维数组嘛。也不会像上面的题解 同时初始化第一列了。
[
[1,3,1],
[1,5,1],
[4,2,1]
]
则一维数组 ,分4种情况,第一个元素,第一行,第一列,中间的元素(不在第一行也非第一列)
第一行 :只要 用当前结点值 + dp数组前一个元素即可
第一列 :当前结点值 + dp数组 当前元素 ,则上一行计算的时候,这列的dp数组的值!
中间的元素:当前结点值 + (左边的或者上面的,因为就这2条路径可以走下来,左边的直接用dp[j-1],至于上面的,则dp[j] 为上一行计算的时候 ,这个列的dp数组的值!)
个人认为 这个难点就在于 搞清楚路径的逻辑,因为他只能向下或者向右。这句话就表示了你要从哪两个元素中比较最小值。至于动态规划的状态转移返程也就根据这个出来。
一维数组 更节省空间。相对二维数组会难以理解一些。主要是数组的复用,当遍历每一行的时候。利用上一行的值进行计算,同时修改已经用过得值,类似于用完了就抛弃掉?思路和二维数组是无差异的。
代码如下:
public int minPathSum(int[][] grid) {
int[] dp = new int[grid[0].length];
for(int i = 0; i < grid.length;i++) {
for(int j = 0;j < grid[0].length;j++) {
if (i == 0 && j != 0) {
dp[j] = grid[i][j] + dp[j-1];
} else if (i != 0 && j == 0) {
dp[j] = grid[i][j] + dp[j];
} else if (i != 0 && j != 0) {
dp[j] = grid[i][j] + Math.min(dp[j-1], dp[j]);
} else {
dp[j] = grid[0][0];
}
}
}
return dp[grid[0].length - 1];
}
上一篇: leetcode第7双周赛
下一篇: 统计学习方法-感知机、k近邻