Leetcode 64. Minimum Path Sum

64. Minimum Path Sum

Total Accepted: 76284
Total Submissions:214404
Difficulty: Medium

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.

思路：优化的部分可以参考Leetcode 62. Unique Paths

代码：
方法一：未优化。

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

方法二：已优化。

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