64. Minimum Path Sum
# Medium
Is very similar to #62.
1. minPath represents minimum path instead of possible paths.
2. minPath initilizes each edge element: minPath[x][y]=grid[x][y].
Solution:
Initilize
minPath[0][0] = grid[0][0]Initilize the edge elements of minPath:
minPath[x][y] = grid[x][y]+grid[0][0]Initilize other elements of minPath:
minPath[x][y] = min(minPath[x-1][y], minPath[x][y-1]) + grid[x][y]
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int i = 1; i < n; i ++)
grid[0][i] += grid[0][i-1];
for(int j = 1; j < m; j ++)
grid[j][0] += grid[j-1][0];
for(int row = 1; row < m; row ++)
for(int col = 1; col < n; col ++) {
grid[row][col] += Math.min(grid[row-1][col], grid[row][col-1]);
}
return grid[m-1][n-1];
}
}class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# initialize minPath
m = len(grid)
n = len(grid[m-1])
minPath = [[-1]*n for i in range(m)]
minPath[0][0] = grid[0][0]
# initialize fixed part of minPath
for x in range(1, m):
minPath[x][0] = grid[x][0] + minPath[x-1][0]
for y in range(1, n):
minPath[0][y] = grid[0][y] + minPath[0][y-1]
# compute other element of minPath
for x in range(1, m):
for y in range(1, n):
minPath[x][y] = min(minPath[x-1][y], minPath[x][y-1]) + grid[x][y]
return minPath[m-1][n-1]Last updated
Was this helpful?