64. Minimum Path Sum

How to solve Minimum Path Sum (LeetCode 64): the approach in brief

The 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.

Pattern

Minimum Path Sum is a Dynamic Programming (DP) Patterns problem, in the 2D Array (Unique Paths on Grid) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Count paths and find optimal paths in grids using 2D dynamic programming.

Approach outline

1. Consider using dynamic programming since the problem involves making optimal choices at each step to minimize a cumulative value.
2. Think about how to represent the problem state: what information do you need at each cell to determine the minimum path sum to that point?
3. Try to build a DP table where each cell stores the minimum path sum to reach that cell from the start, using only moves from the left or above.

Complexity

The reference solution runs in O(m * n) time and O(1) space.

Asked at

Minimum Path Sum has been reported in interviews at Google, Amazon, Goldman Sachs, Facebook, Apple, Snapchat, Tesla.