64.Minimum_Path_Sum(Medium).md

64. Minimum Path Sum (Medium)

Date and Time: Nov 18, 2024, 17:56 (EST)

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

Question:

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 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Output: 7

Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[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

Walk-through:

Build a dp table with size m x n, we notice that the path from the top left to bottom right will lead to a sum that dp[r][c] = grid[r][c] + min(dp[r+1][c], dp[r][c-1]]), which is the current value in grid[r][c] + the minimum of this entry's dp table's left-entry and its dp table's above-entry.

The base cases will be our first row and the first column, in the first row, it can only take the sum of current entry's left neighbor, dp[0][c] = grid[0][c] + dp[0][c-1]. The first column can only take its previous row's values, so we update dp[r][0] = grid[r][0] + dp[r-1][0].

For the rest, we build the table from left to right, top to bottom, and we return the bottom-right entry from the dp table to be the output.

DP Solution:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # Recurrence Relation: dp[r][c] = grid[r][c] + min(dp[r+1][c], dp[r][c-1])
        # Base case: 1st row can only take its left, 1st col can only takes its top
        # dp
        # 1 4 5
        # 2 7 6
        # 6 8 7
        
        # top row: 1, 3+1(left), 1+4(left)
        # 2nd row: 1+1(above), 5+min(2(left), 4(above))=7, 1+min(5(above), 7(left))=6
        # 3rd row: 4+2(above), min(2+6(left), 2+7(above)=8, 1+min(8(left), 6(above))=7)

        # TC: O(m x n), SC: O(m x n)
        rows, cols = len(grid), len(grid[0])
        dp = [[0] * cols] * rows
        dp[0][0] = grid[0][0]
        # 0th row
        for c in range(1, cols):
            dp[0][c] = grid[0][c] + dp[0][c-1]
        # 0th col
        for r in range(1, rows):
            dp[r][0] = grid[r][0] + dp[r-1][0]
        # Recurrent Relation
        for r in range(1, rows):
            for c in range(1, cols):
                dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
        return dp[-1][-1]

Time Complexity: $O(m * n)$
Space Complexity: $O(m * n)$

Optimized 1D DP Solution:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 1D DP, optimized with dp[] with n
        # Base case: dp = [1, 4, 5]
        # Recurrence Relation:
        # dp[0] += grid[r][0], 0th col only takes its top
        # dp[c] = grid[r][c] + min(dp[c-1], dp[c])

        # TC: O(m x n), SC: O(n)
        rows, cols = len(grid), len(grid[0])
        dp = grid[0]
        # 0th row base case
        for c in range(1, cols):
            dp[c] += dp[c-1]
        # Recurrent Relation
        for r in range(1, rows):
            dp[0] += grid[r][0]
            for c in range(1, cols):
                dp[c] = grid[r][c] + min(dp[c], dp[c-1])
        return dp[-1]

Time Complexity: $O(m * n)$
Space Complexity: $O(n)$