Link: https://leetcode.com/problems/minimum-path-sum/

Solution:

Topics: DP

Intuition
Pretty trivial DP problem, of course Dijkstra’s also works here but its way overkill. We should immediately understand this as DP because at each node we have to make a decision: go right or go down. Which one do we choose? We don’t know, and can’t know until we reach the end.

For example:

1 1 1 1
1 2 2 3
1 1 1 1

We see that in the above matrix, going all the way down/right and all the way right/down has the some cost until the right/down path reaches the 3. So it stands to reason that we must consider both options until the termination of each respective path.

Implementation

def min_path(grid):
	@cache
	def dfs(i, j):
		if i == len(grid) or j == len(grid[0]):
			return float('inf')
		if i == len(grid)-1 and j == len(grid[0])-1:
			return grid[i][j]
		right = grid[i][j] + dfs(i+1, j)
		down = grid[i][j] + dfs(i, j+1)
		return min(right, down)
	return dfs(0, 0)
 
#time: o(n*m)
#memory: o(n*m)

Visual

Review 1
Too easy. Move on.

review