LeetCode #64 Minimum Path Sum

Posted on | Post modified | In , , , , , ,

Problem

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
2
3
4
5
6
7
8
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Solution

Method: Dynamic Programming

Time Complexity: O(m * n)

Space Complexity: O(m * n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row = len(grid)
        col = len(grid[0])
        table = [[0] * col for _ in range(row)]
        table[0][0] = grid[0][0]
        
        for idx in range(1, row):
            table[idx][0] = table[idx - 1][0] + grid[idx][0]
        
        for idx in range(1, col):
            table[0][idx] = table[0][idx - 1] + grid[0][idx]

        for idx_r in range(1, row):
            for idx_c in range(1, col):
                table[idx_r][idx_c] = min(table[idx_r - 1][idx_c], table[idx_r][idx_c - 1]) + grid[idx_r][idx_c]
        
        return table[-1][-1]

or

Method: Dynamic Programming

Time Complexity: O(m * n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row = len(grid)
        col = len(grid[0])
        
        for idx in range(1, row):
            grid[idx][0] = grid[idx - 1][0] + grid[idx][0]
        
        for idx in range(1, col):
            grid[0][idx] = grid[0][idx - 1] + grid[0][idx]

        for idx_r in range(1, row):
            for idx_c in range(1, col):
                grid[idx_r][idx_c] = min(grid[idx_r - 1][idx_c], grid[idx_r][idx_c - 1]) + grid[idx_r][idx_c]
        
        return grid[-1][-1]