Leetcode-64 Minimum Path Sum

发表于 | 分类于 | 次

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1

1
2
3
4
5
6
7
8
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

解题思路

动态规划：要到达位置 [m,n]，必须先到达位置 [m,n-1] 或 [m-1,n]，其最小路径和为到达 [m,n-1] 或 [m-1,n] 的最小值加上位置 [m,n] 的数值。

复杂度分析

  • 时间复杂度：$O(mn)$。
  • 空间复杂度：$O(1)$，可直接利用 grid。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
	int minPathSum(vector<vector<int>>& grid) {
		for (int i = 0; i < grid.size(); i++) {
			for (int j = 0; j < grid[0].size(); j++) {
				if (i == 0 && j > 0)
					grid[i][j] += grid[i][j - 1];
				else if (j == 0 && i > 0)
					grid[i][j] += grid[i - 1][j];
				else if (i > 0 && j > 0)
					grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
			}
		}
		return grid[grid.size() - 1][grid[0].size() - 1];
	}
};