Minimum Path Sum 最小路径和
题目：
给定一个包含非负整数的?m?x?n?网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入: [ ? [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
解题思路：
DP问题，每次更新一行的最小路径值。
空间复杂度O(n)，时间复杂度O(n^2)。
代码实现：
class Solution {
public int minPathSum(int[][] grid) {
int[] min = new int[grid[0].length];
// 初始化
for (int i = 0; i < grid[0].length; i ++) {
if (i == 0) { min[i] = grid[0][i]; continue; }
min[i] = min[i - 1] + grid[0][i];
}
for (int i = 1; i < grid.length; i ++) {
for (int j = 0; j < grid[i].length; j ++) {
if (j == 0) {
min[j] += grid[i][j];
continue;
}
min[j] = Math.min(min[j], min[j - 1]) + grid[i][j];
}
}
return min[min.length - 1];
}
}
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻