[LeetCode] 64. Minimum Path Sum (Medium/Python)

Minimum Path Sum - LeetCode

Above is the link to the problem.

 

Problem

Given a m x n grid filled with non-negative numbers,

find a path from the top left to the bottom right,

which minimizes the sum of all numbers along its path.

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

 

Example

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.

 

Analysis

Let's think about the below 4x4 grid example.

We can solve this problem by finding the minimum summation path for each grid. 

The grid of the column[0] and row[0] summation counts easily because there is only one path.

about column[0]

about row[0]

Then, we can choose the minimum path for each grid from the top-left grid to the bottom-right grid.

 

 

Code

 

 

This code gets the top 39.27% of time complexity and uses 15.7MB of memory