Minimum Path Sum (Leetcode 64)
Problem Link: https://leetcode.com/problems/minimum-path-sum/
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# Traverse from bottom right to top left
m=len(grid)
n=len(grid[0])
dp=[[0 for i in range(n)] for j in range(m)]
for i in range(m-1,-1,-1):
for j in range(n-1,-1,-1):
if(i==m-1 and j==n-1):
dp[i][j]=grid[i][j]
elif(i==m-1):
dp[i][j]=grid[i][j]+dp[i][j+1]
elif(j==n-1):
dp[i][j]=grid[i][j]+dp[i+1][j]
else:
dp[i][j]=min(dp[i+1][j],dp[i][j+1])+grid[i][j]
return dp[0][0]
Last updated