Leetcode 64. Minimum Path Sum (Python)

Related Topic

Dynamic-Programming.

Description

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.

Sample I/O

Example 1

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Note:

You can only move either down or right at any point in time.

Methodology

This question solved by Dynamic Programming. It is similar with question 62.Unique Paths.

1. Find the base case: The base case can be original 2D list, we will replace the value of each cell with minimum sum. However, to use dynamic programming, we need to sum up each cell of the first row and first column with it’s previous cell.

2. Find the pattern:

   This question is actually easier than qustion 62, you do not need to create a dp list to store the value. For each target cell, it is either from right or down, all we need to do is smaller sum from right and down, then add the minimum sum to the current target

3. Answer:

   When reach to the bottom-right corner, then number in the bottom-right corner will be the answer.

Code

def minPathSum(self, grid):
        if not grid: return
        m, n = len(grid), len(grid[0])
        for i in range(1,m):
            grid[i][0] += grid[i-1][0]
        for j in range(1,n):
            grid[0][j] += grid[0][j-1]
        for i in range(1,m):
            for j in range(1,n):
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
        return grid[m-1][n-1]

BigO

Init the first row and first column that will cost O(m-1+n-1). Then iterate all 2D dp array, it will cost O((m-1)*(n-1)). In total will cost (m^2-2mn+m+n-1) which generally is O(m^2-2mn)