Minimum Path Sum

How it works

When filling the DP table row by row (from bottom to top), we only need the current row and the row below. In fact, since we process columns right to left, we can overwrite the same 1D array. The value at dp[c] represents the minimum path sum from (r+1, c), and dp[c+1] represents the path from (r, c+1). After updating, dp[c] will hold the result for (r, c).

Steps

1. Create a 1D array dp of size COLS+1 initialized to infinity.
2. Set dp[COLS-1] = 0 as the base case.
3. For each row from bottom to top:
   • For each column from right to left: dp[c] = grid[r][c] + min(dp[c], dp[c+1]).
4. Return dp[0].

Complexity

• Time complexity: O(m * n)
• Space complexity: O(n)

Where m is the number of rows and n is the number of columns.

Things to watch for

Incorrect Boundary Initialization

When using bottom-up DP, the extra row and column must be initialized to infinity (or a very large value), except for one cell that serves as the base case. Initializing boundaries to 0 instead of infinity causes the algorithm to prefer going out of bounds, producing incorrect minimum sums.

Integer Overflow with MAX_VALUE

When adding grid[r][c] to Integer.MAX_VALUE (or equivalent), the result overflows to a negative number, which then incorrectly becomes the minimum. Use a large but safe value like 1 << 30 instead, or add overflow checks before the addition.

Wrong Iteration Direction in Space-Optimized Solution

In the 1D DP optimization, the iteration direction matters. When processing from bottom-right to top-left, you must iterate columns right-to-left within each row. Iterating left-to-right overwrites values before they are used, corrupting the DP state and producing wrong answers.

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        dp = [float("inf")] * (COLS + 1)
        dp[COLS - 1] = 0

        for r in range(ROWS - 1, -1, -1):
            for c in range(COLS - 1, -1, -1):
                dp[c] = grid[r][c] + min(dp[c], dp[c + 1])

        return dp[0]

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int ROWS = grid.size(), COLS = grid[0].size();
        vector<int> dp(COLS + 1, INT_MAX);
        dp[COLS - 1] = 0;

        for (int r = ROWS - 1; r >= 0; r--) {
            for (int c = COLS - 1; c >= 0; c--) {
                dp[c] = grid[r][c] + min(dp[c], dp[c + 1]);
            }
        }

        return dp[0];
    }
};