The description of the question is included in the following link:
https://leetcode.com/problems/minimum-path-sum/
My Code
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
RowNum = len(grid);
ColNum = len(grid[0]);
Mat = [[0]*ColNum for _ in range(RowNum)];
Mat[0][0] = grid[0][0];
for row in range(RowNum):
if row == 0:
for col in range(1,ColNum):
Mat[row][col] = grid[row][col]+ Mat[row][col-1];
else:
for col in range(ColNum):
if col ==0 :
Mat[row][col] = grid[row][col]+Mat[row-1][col];
else:
Mat[row][col] = min(Mat[row][col-1],Mat[row-1][col])+ grid[row][col];
return Mat[RowNum-1][ColNum-1];
Explanation:
The idea behind the code is really simple. For each block, there are two ways to go in: from the top or from left block. We then just need to find the minimum value between these two then add the number in the block to have the minimum value that can go to that block. So we keep this procedure and then we may find the minimum value of the block we want.