64. Minimum Path Sum

29 Dec 64. Minimum Path Sum

Posted at 17:01h in Coding by
0 Likes

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] <= 100

 

Dynamic programming is all about breaking the whole problem into smaller problems in which you can then minimize, which will result in the whole problem being minimized. In this question, we should notice that the minimum path sum for each cell is the smaller value between the cell itself plus the cell above it or the the cell itself plus the cell to the left of it. So, as you visit each future cell and refer to previous cells to the left and above you, you know that those cells have been optimized to have the minimum path sum for that index – thus obtaining the most optimal path.

For example,

[1,3,1],
[1,5,1],
[4,2,1]
 
  • grid[0][1], there is a cell to the left of it (grid[0][0] = 1) and no cell above it, this means we know that the minimum path sum for this cell is at best 4 (3 + 1).
  • grid[0][2], similar to grid[0][1], at best is 5 (1 + 4)
  • grid[1][0], there is a cell above (grid[0][0] = 1) and no cell to the left of it, this means we know that the minimum path sum for this cell is at best 2 (1 + 1).
  • grid[1][1], there is a cell above and also a cell to the left of it, we will need to add a cell (grid[0][1] = 4 or grid[1][0] = 2) that will result in the current cell having the smallest sum possible. It is ideal to add grid[1][0], thus the minimum path sum for this cell is at best 7 (2 + 5).
  • grid[1][2], similar to grid[1][1], at best is 6 (1 + 5)
  • grid[2][0], similar to grid[1][0], at best is 6 (4 + 2)
  • grid[2][1], similar to grid[1][1], at best is 8 (2 + 6)
  • grid[2][2], similar to grid[1][1], at best is 7 (1 + 6)

The resulting DP array – you can put your calculated results for each cell in a seperate 2D array or do it in-place (which I did).

[1,4,5],
[2,7,6],
[6,8,7]
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if j == 0 and i > 0 :
                    grid[i][j] = grid[i-1][j] + grid[i][j]
                elif i == 0 and j > 0 :
                    grid[i][j] = grid[i][j] + grid[i][j-1]
                elif i > 0 and j > 0:
                    grid[i][j] = min(grid[i][j]+grid[i-1][j], grid[i][j]+grid[i][j-1])
        return grid[-1][-1]
No Comments

Post A Comment