Medium

Minimum Path Sum

055

Given a non-negative grid, return the minimum path sum from top-left to bottom-right moving only right or down.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      3,
      1
    ],
    [
      1,
      5,
      1
    ],
    [
      4,
      2,
      1
    ]
  ]
}

Output
7

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

Classic grid DP. From each cell, we can go right or down. Take the cheaper path and add current cell's value.

Reveal reference solution +

pythonREFERENCE

def minPathSum(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    @cache
    def dp(i, j):
        if i == m-1 and j == n-1: return grid[i][j]
        if i >= m or j >= n: return inf
        return grid[i][j] + min(dp(i+1, j), dp(i, j+1))

    return dp(0, 0)

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗