Minimum Path Sum 最小路径和
18-06-28
Minimum Path Sum 最小路径和。给定一个包含非负整数的?m?x?n?网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
题目:
给定一个包含非负整数的?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]; } }
相关文章
最新文章
热点推荐