minPathSum.py

'''
64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
'''
def minPathSum(self, grid: List[List[int]]) -> int:
  m = len(grid)
  n = len(grid[0])
  dp = [[0 for i in range(n)] for j in range(m)]
  dp[0][0] = grid[0][0]
  for i in range(m):
      for j in range(n):
          if i>0 and j>0:
              dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
          elif i>0:
              dp[i][j] = dp[i-1][j] + grid[i][j]
          elif j >0:
              dp[i][j] = dp[i][j-1] + grid[i][j]
  return dp[m-1][n-1]
  
  '''
  Time complexity = O(mn)
  Space complexity = O(mn)
  '''