64. Minimum Path Sum | LeetCode Solution
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:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
class Solution {public: int minPathSum(vector<vector<int>>& grid) { int m=grid[0].size(); vector<int>prev(m,0); for(int i=0; i<grid.size(); i++){ vector<int>curr(m,0); for(int j=0; j<grid[0].size(); j++){ if(i==0 && j==0){ curr[j]=grid[i][j]; } else{ int up=grid[i][j]; if(i>0)up+=prev[j]; else up+=1e9; int left=grid[i][j]; if(j>0)left+=curr[j-1]; else left+=1e9; curr[j]=min(left,up); } } prev=curr; } return prev[grid[0].size()-1]; }};
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:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]] Output: 12
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m=grid[0].size();
vector<int>prev(m,0);
for(int i=0; i<grid.size(); i++){
vector<int>curr(m,0);
for(int j=0; j<grid[0].size(); j++){
if(i==0 && j==0){
curr[j]=grid[i][j];
}
else{
int up=grid[i][j];
if(i>0)up+=prev[j];
else up+=1e9;
int left=grid[i][j];
if(j>0)left+=curr[j-1];
else left+=1e9;
curr[j]=min(left,up);
}
}
prev=curr;
}
return prev[grid[0].size()-1];
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.