Minimum Path Sum: LeetCode 64 Solution Explained

Minimum Path Sum (#64) is one of the cleanest introductions to weighted grid DP on LeetCode. If you have already solved Unique Paths (#62), you know how to count the number of ways to reach the bottom-right corner of a grid. Minimum Path Sum asks a different question: instead of counting paths, find the path with the lowest total cost.

This shift from counting to optimizing is exactly the kind of evolution interviewers test. You keep the same grid structure, the same movement rules (right or down only), but now every cell has a weight. Your DP recurrence changes from addition of counts to selection of minimums.

Companies like Google, Amazon, and Microsoft use this problem because it bridges the gap between basic grid traversal and real-world optimization problems like minimum cost routing. If you can solve Minimum Path Sum cleanly, you are ready for harder variants like Dungeon Game (#174) and Cherry Pickup (#741).

You are given an m x n grid filled with non-negative integers. Starting from the top-left corner, you need to reach the bottom-right corner. At each step, you can only move right or down. The goal is to find the path that minimizes the total sum of all cells along the way.

The key constraint is the movement restriction. Because you can only move right or down, you will always take exactly (m - 1) + (n - 1) steps to reach the destination. Every path has the same length — what differs is which cells you pass through and their accumulated cost.

Consider the classic example: grid = [[1,3,1],[1,5,1],[4,2,1]]. The minimum path goes 1 -> 3 -> 1 -> 1 -> 1, giving a total of 7. Notice that the path avoids the expensive center cell (5) by going right first, then down.

The recurrence relation is elegant: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Each cell stores the minimum cost to reach it. You can only arrive from the cell above or the cell to the left, so you take the cheaper of those two options and add the current cell value.

Before filling the interior, you need to handle the base cases. The first row can only be reached by moving right, so dp[0][j] = dp[0][j-1] + grid[0][j]. Similarly, the first column can only be reached by moving down, so dp[i][0] = dp[i-1][0] + grid[i][0]. These prefix sums form the boundary conditions.

Once the boundaries are set, you iterate through the remaining cells row by row (or column by column). The final answer sits at dp[m-1][n-1]. The time complexity is O(mn) because you visit every cell exactly once. The space complexity is also O(mn) if you use a separate DP table.

Here is the trick that impresses interviewers: you do not need a separate DP table at all. Since you only read each cell once and never look back, you can modify the input grid directly. Set grid[i][j] += min(grid[i-1][j], grid[i][j-1]) as you go, and the grid itself becomes your DP table.

This turns O(mn) extra space into O(1) extra space. The trade-off is that you mutate the input, which some interviewers will ask about. If the input must be preserved, mention that you can either clone the grid first or use a single-row rolling array for O(n) space.

The rolling array approach keeps only two rows in memory at a time — the previous row and the current row. Since dp[i][j] depends only on dp[i-1][j] (directly above) and dp[i][j-1] (to the left), a single row that you update left to right is sufficient. This is the same space optimization pattern used in Unique Paths and many other 2D DP grid problems.

Let us trace through the example grid [[1,3,1],[1,5,1],[4,2,1]] to see the DP table build up. Start with dp[0][0] = 1. Fill the first row: dp[0][1] = 1+3 = 4, dp[0][2] = 4+1 = 5. Fill the first column: dp[1][0] = 1+1 = 2, dp[2][0] = 2+4 = 6.

Now fill the interior. dp[1][1] = 5 + min(4, 2) = 5 + 2 = 7. dp[1][2] = 1 + min(5, 7) = 1 + 5 = 6. dp[2][1] = 2 + min(7, 6) = 2 + 6 = 8. dp[2][2] = 1 + min(6, 8) = 1 + 6 = 7.

The final DP table looks like: [[1,4,5],[2,7,6],[6,8,7]]. The answer is dp[2][2] = 7. If you trace back from the answer, the optimal path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2), which corresponds to values 1 + 3 + 1 + 1 + 1 = 7.

A 1x1 grid is the simplest edge case — the answer is just grid[0][0]. A single row means you can only move right, so the answer is the sum of all elements. A single column means you can only move down, same idea. These base cases should be handled naturally by your DP initialization, not as special if-statements.

What if all values are the same? Then every path has the same cost: value * (m + n - 1). This is a good sanity check for your implementation. What about very large values? Since the grid contains non-negative integers and you are summing them, watch for integer overflow in languages like C++ or Java (not an issue in Python or JavaScript).

A common follow-up is Minimum Path Sum with obstacles, which combines this problem with Unique Paths II (#63). Cells marked as obstacles cannot be traversed. You handle this by setting dp[i][j] = infinity for obstacle cells. Another variant asks you to print the actual path, not just the sum — trace back from dp[m-1][n-1] by choosing the smaller neighbor at each step.

Minimum Path Sum is the gateway to weighted grid DP. Once you understand that dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), you can apply the same template to dozens of problems. The core insight — choosing the optimal sub-path at each cell — is the heart of dynamic programming.

This problem is a direct stepping stone to harder challenges. Dungeon Game (#174) reverses the direction — you fill the DP table from bottom-right to top-left because the constraint depends on future cells. Cherry Pickup (#741) adds a second traversal, turning the problem into a 3D DP challenge. Triangle (#120) applies the same min-path logic to a triangular grid.

Use YeetCode flashcards to drill the weighted grid DP pattern until the recurrence becomes second nature. When you see a grid problem in an interview, your first instinct should be to ask: can I define dp[i][j] as the optimal value to reach this cell? If the answer is yes, Minimum Path Sum is your template.