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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

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

Solutions:
class Solution:

	def minPathSum(self, grid):
		(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):
		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):
		M = len(grid)
		if M == 0:
			return 0
		N = len(grid[0])
		if N == 0:
			return 0
		INF = float('inf')
		mem = {}

		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):
		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):
		max_row = len(grid) - 1
		max_col = len(grid[0]) - 1
		helper_grid = [[0] * len(grid[0]) for _ in range(len(grid))]
		helper_grid[max_row][max_col] = grid[max_row][max_col]
		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]
		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])
		return helper_grid[0][0]


class Solution:

	def minPathSum(self, grid):
		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):
		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):
		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):
		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):
		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):
		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]


class Solution:

	def minPathSum(self, grid):
		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):
		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)