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.

Example:


Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Difficulty: interview

Starter code:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         m, n = len(grid), len(grid[0])
         dp = [0] + [float('inf')] * (n-1)
         for i in range(m):
             dp[0] = dp[0] + grid[i][0]
             for j in range(1, n):
                 dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
         return dp[-1]

class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         m = len(grid)
         n = len(grid[0])
         dp = [grid[0][j] for j in range(n)]
         
         for j in range(1, n):
             dp[j] += dp[j-1]
         for i in range(1, m):
             for j in range(n):
                 if j == 0:
                     dp[j] += grid[i][j]
                 else:
                     dp[j] = min(grid[i][j]+dp[j-1], grid[i][j]+dp[j])
         return dp[-1]


class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         M = len(grid)
         if M == 0:
             return 0
         N = len(grid[0])
         if N == 0:
             return 0
         
         INF = float('inf')
         mem = {}
         
         # O(M*N)
         def min_path(i,j):
             if i == M-1 and j == N-1:
                 return grid[i][j]
             if (i,j) in mem:
                 return mem[(i,j)]
             
             min_sum = INF
             if i < M-1:
                 min_sum = min_path(i+1, j)
             if j < N-1:
                 min_sum = min(min_sum, min_path(i, j+1))
             
             mem[(i,j)] = grid[i][j] + min_sum
             return mem[(i,j)]
         
         return min_path(0, 0)
             
         
         
         
         
         
         
         
         
         
         
         


class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         m = len(grid)-1
         n = len(grid[0])-1
         dic = dict()
         s = self.minPathSumHelper(grid, 0, 0, m,n, dic)
         return s
     
     def minPathSumHelper(self, grid, i,j, m,n, dic):
         
         if (i, j, m, n) in dic:
             return dic[(i, j, m, n)]
         
         if i>m or j>n:
             return 0
         elif i==m:
             dic[(i, j, m, n)] = self.minPathSumHelper(grid, i, j+1, m, n, dic)+grid[i][j]
             return dic[(i, j, m, n)]
         elif j==n:
             dic[(i, j, m, n)] = self.minPathSumHelper(grid, i+1, j, m, n, dic)+grid[i][j]
             return dic[(i, j, m, n)]
         else:
             dic[(i, j, m, n)] = min(self.minPathSumHelper(grid, i+1, j, m,n, dic), self.minPathSumHelper(grid, i, j+1, m, n, dic))+grid[i][j]
             return dic[(i, j, m, n)]
         


class Solution(object):
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         max_row = len(grid) - 1  # rows
         max_col = len(grid[0]) - 1  # columns
         helper_grid = [[0]*(len(grid[0])) for _ in range(len(grid))]
         helper_grid[max_row][max_col] = grid[max_row][max_col]
         # fill max row and max column
         for i in range(max_col - 1, -1, -1):
             helper_grid[max_row][i] = grid[max_row][i] + helper_grid[max_row][i + 1]
         for i in range(max_row - 1, -1, -1):
             helper_grid[i][max_col] = grid[i][max_col] + helper_grid[i + 1][max_col]
 
         # fill the rest
         for col in range(max_col - 1, -1, -1):
             for row in range(max_row - 1, -1, -1):
                 helper_grid[row][col] = grid[row][col] + min(helper_grid[row+1][col], helper_grid[row][col+1])
         # for row in helper_grid:
         #     print(row)
         return helper_grid[0][0]


class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         if not grid:
             return 0
         row_count = len(grid)
         col_count = len(grid[0])
         for i in range(1, row_count):
             grid[i][0] += grid[i-1][0]
         for i in range(1, col_count):
             grid[0][i] += grid[0][i-1]
         for row in range(1, row_count):
             for col in range(1, col_count):
                 grid[row][col] += min(grid[row-1][col], grid[row][col-1])
         return grid[-1][-1]

class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         if not grid:
             return 0
         row,col = len(grid),len(grid[0])
         dp = [0 for _ in range(col)]
         dp[0] = grid[0][0]
 
         for i in range(1,col):
             dp[i] = dp[i-1] + grid[0][i]
 
         for i in range(1,row):
             for j in range(0,col):
                 dp[j] = dp[j] + grid[i][j] if j==0 else min(dp[j-1],dp[j])+grid[i][j]
 
         return dp[-1]

class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         if not grid:
             return 0
         row_count = len(grid)
         col_count = len(grid[0])
         dp = [[0 for _ in range(col_count)] for _ in range(row_count)]
         dp[0][0] = grid[0][0]
         if row_count == col_count and col_count == 1:
             return dp[-1][-1]
         for row in range(row_count):
             for col in range(col_count):
                 if row == 0 and col >= 1:
                     dp[row][col] = dp[row][col-1] + grid[row][col]
                 elif col == 0 and row >= 1:
                     dp[row][col] = dp[row-1][col] + grid[row][col]
                 else:
                     dp[row][col] = min(dp[row-1][col], dp[row][col-1]) + grid[row][col]
         return dp[-1][-1]

class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         m = len(grid)
         n = len(grid[0])
         s = [[0 for j in range(n)] for i in range(m)]
         s[0][0] = grid[0][0]
         
         for i in range(1, m):
             s[i][0] = s[i-1][0] + grid[i][0]
 
         for j in range(1, n):
             s[0][j] = s[0][j-1] + grid[0][j]
 
         for i in range(1, m):
             for j in range(1, n):
                 s[i][j] = min(s[i-1][j]+grid[i][j], s[i][j-1]+grid[i][j])
         
 
         return s[m-1][n-1]


class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         height = len(grid)
         width = len(grid[0])
         step_num = (height + width) - 2
         for step in range(1, step_num+1):
             for row in range(height):
                 col = step - row
                 if 0 <= row < height and 0 <= col < width:
                     if not row:
                         grid[row][col] += grid[row][col-1]
                     elif not col:
                         grid[row][col] += grid[row-1][col]
                     else:
                         grid[row][col] += min(grid[row][col-1], grid[row-1][col])
         return grid[-1][-1]

class Solution:
     def minPathSum(self, grid): 
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         xx=len(grid)-1
         yy=len(grid[0])-1
         gridv=[[0 for j in range(len(grid[0]))] for i in range(len(grid))]
         gridv[xx][yy]=grid[xx][yy]
         for i in range(xx,-1,-1):
             for j in range(yy,-1,-1):
                 if i==xx:
                     if j==yy:
                          gridv[i][j]=grid[xx][yy]
                     else:
                          gridv[i][j]=grid[i][j]+gridv[i][j+1]
                 elif j==yy:
                     if i==xx:
                          gridv[i][j]=grid[xx][yy]
                     else:
                          gridv[i][j]=grid[i][j]+gridv[i+1][j]
                 else:            
                     gridv[i][j]=min(gridv[i+1][j]+grid[i][j],gridv[i][j+1]+grid[i][j])
         print(grid)
         print(gridv)
         return gridv[0][0]
     
         """"
         if(len(grid)==1 or len(grid[0])==1):
             return sum(sum(grid,[]))
         if
         return grid[0][0]+min(self.minPathSum(grid[1:],x,y+1),self.minPathSum([grids[1:] for grids in grid],x+1,y))
         """""

class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         col = len(grid[0])
         row = len(grid)
         minSum = [[0 for x in range(col)] for y in range(row)]
         
         for i in range(row):
             for j in range(col):
                 add = 0
                 if i-1 >= 0 and j-1 >= 0:
                     add = min(minSum[i-1][j], minSum[i][j-1])
                 elif i-1 >= 0:
                     add = minSum[i-1][j]
                 elif j-1 >= 0:
                     add = minSum[i][j-1]
                 minSum[i][j] = grid[i][j] + add
         
         return minSum[-1][-1]
                 
         


class Solution:
     def minPathSum(self, grid):
         """
         :type grid: List[List[int]]
         :rtype: int
         """
         m = len(grid)
         n = len(grid[0])
         if m == 0 or n == 0: return 0
         
         memory = [[0 for _ in range(n)] for _ in range(m)]
         
         def minSum(grid,x,y,n,m):
             if x==0 and y==0: return grid[0][0]
             if x<0 or y<0: return float("inf")
             if memory[y][x] > 0: return memory[y][x]
             memory[y][x] = grid[y][x] + min(minSum(grid,x-1,y,n,m),minSum(grid,x,y-1,n,m))
             return memory[y][x]
             
         return minSum(grid,n-1,m-1,n,m)