Minimum Path Sum — Grid DP
Advertisement
Problem
Find minimum sum path from top-left to bottom-right (right/down only).
Solutions
Python
class Solution:
def minPathSum(self, grid: list[list[int]]) -> int:
m,n=len(grid),len(grid[0])
for i in range(m):
for j in range(n):
if i==0 and j==0: continue
elif i==0: grid[i][j]+=grid[i][j-1]
elif j==0: grid[i][j]+=grid[i-1][j]
else: grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
return grid[m-1][n-1]
C++
class Solution {
public:
int minPathSum(vector<vector<int>>& g){
int m=g.size(),n=g[0].size();
for(int i=0;i<m;i++) for(int j=0;j<n;j++){
if(!i&&!j) continue;
else if(!i) g[i][j]+=g[i][j-1];
else if(!j) g[i][j]+=g[i-1][j];
else g[i][j]+=min(g[i-1][j],g[i][j-1]);
}
return g[m-1][n-1];
}
};
Complexity
- Time: O(m*n) | Space: O(1) (in-place)
Advertisement
← Previous
Triangle — Bottom-Up 1D DP