Given a grid of non-negative integers, find the path from the top-left corner to the bottom-right corner that miniimzes the sum of the values along the path. Movement is restricted to only down or right directions.

Example 1: Input: [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: The path 1→3→1→1→1 yields the minimum sum.

Example 2: Input: [[1,2,3],[4,5,6]] Output: 12

Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 200

Approach 1: Dynamic Programming

1. Define dp array where dp[i][j] represents the minimum path sum to reach (i,j) from the top-left corner.
2. Recurrence relation: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3. Initialize dp[0][0] = grid[0][0]. For first row and column, compute cumulative sums.
4. Traverse the grid starting from (1,1), computing dp[i][j] based on previous values.

Example code:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [[0]*cols for _ in range(rows)]
        dp[0][0] = grid[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, cols):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, rows):
            for j in range(1, cols):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

Time complexity: O(rows * cols) Space complexity: O(rows * cols)

Approach 2: Space Optimization by Modifying the Grid

Instead of using a separate dp array, modify the input grid directly.

Example code:

class Solution:
    def minPathSum(self, grid: [[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0 and j == 0:
                    continue
                elif i == 0:
                    grid[i][j] = grid[i][j-1] + grid[i][j]
                elif j == 0:
                    grid[i][j] = grid[i-1][j] + grid[i][j]
                else:
                    grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
        return grid[-1][-1]

Time complexity: O(rows * cols) Space complexity: O(1)

Approach 3: Depth-First Search with Memoization

Use recursion with memoization to explore all possible paths and track the minimum sum.

Example code:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        @lru_cache
        def dfs(r, c):
            if r == 0 and c == 0:
                return grid[r][c]
            if r == 0:
                return dfs(r, c-1) + grid[r][c]
            if c == 0:
                return dfs(r-1, c) + grid[r][c]
            return min(dfs(r-1, c), dfs(r, c-1)) + grid[r][c]
        return dfs(rows-1, cols-1)

Time complexity: O(rows * cols) Space complexity: O(rows * cols)