1def minPathSum(grid):
2 m, n = len(grid), len(grid[0])
3 dp = [[0] * n for _ in range(m)]
4
5 # Base case
6 dp[0][0] = grid[0][0]
7
8 # Fill first row
9 for j in range(1, n):
10 dp[0][j] = dp[0][j - 1] + grid[0][j]
11
12 # Fill first column
13 for i in range(1, m):
14 dp[i][0] = dp[i - 1][0] + grid[i][0]
15
16 # Fill rest of DP table
17 for i in range(1, m):
18 for j in range(1, n):
19 dp[i][j] = grid[i][j] + min(
20 dp[i - 1][j], # from top
21 dp[i][j - 1] # from left
22 )
23
24 return dp[m - 1][n - 1]