Minimum Path Sum: cheapest path through a weighted grid

• Grid DP – dp[i][j] stores the minimum total cost to reach cell (i, j) from the top-left.
• Transition – dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) for interior cells.
• Base cases – first row and first column are prefix sums (only one way to reach them).
• Answer – dp[m-1][n-1] holds the minimum path sum.
• Complexity – O(m * n) time, O(n) space with a rolling row or O(1) by overwriting the input.

What is the Minimum Path Sum problem?

You have an m-by-n grid where each cell contains a non-negative cost. Starting at the top-left corner and moving only right or down, find the path to the bottom-right corner that minimises the total cost. The cost of a path is the sum of all cell values along it.

In banking, this is routing funds through a network of correspondent banks where each bank charges a fee, and you want the cheapest route.

How does the DP recurrence work?

At each cell (i, j), the robot arrives from either the cell above (i-1, j) or the cell to the left (i, j-1). The minimum cost to reach (i, j) is the cell's own cost plus the cheaper of the two incoming paths.

package com.bank.service;

public class FundsRoutingService {

    public static int minimumPathSum(int[][] fees) {
        int m = fees.length, n = fees[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = fees[0][0];

        // First column: can only come from above
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + fees[i][0];
        }

        // First row: can only come from the left
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + fees[0][j];
        }

        // Interior cells: min of above and left
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = fees[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] fees = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        System.out.println("Minimum routing fee: " + minimumPathSum(fees));
    }
}

Minimum routing fee: 7

Why does greedy fail here?

A greedy approach that always picks the cheapest next cell can miss a better overall route. The greedy choice is locally optimal but not globally optimal.

// Grid:    1  3  1
//          1  5  1
//          4  2  1
// Greedy from (0,0): go right to 3? No, go down to 1.
// From (1,0): go right to 5? Or down to 4?
// Greedy picks 4 (down), then 2 (right), then 1 (right) = 1+1+4+2+1 = 9
// Optimal: 1 -> 3 -> 1 -> 1 -> 1 = 7
// Greedy fails because it avoids the 3 but hits the 4.

How do you optimise space?

Since each cell depends only on the cell above (previous row) and the cell to the left (current row), you can use a single rolling row. You can also overwrite the input grid in place for O(1) extra space if mutation is acceptable.

public static int minimumPathSumOptimised(int[][] fees) {
    int m = fees.length, n = fees[0].length;
    int[] dp = new int[n];
    dp[0] = fees[0][0];

    // First row
    for (int j = 1; j < n; j++) dp[j] = dp[j - 1] + fees[0][j];

    // Remaining rows
    for (int i = 1; i < m; i++) {
        dp[0] += fees[i][0]; // first column: only from above
        for (int j = 1; j < n; j++) {
            dp[j] = fees[i][j] + Math.min(dp[j], dp[j - 1]);
            // dp[j] (before update) = value from above
            // dp[j-1] (already updated) = value from left
        }
    }
    return dp[n - 1];
}

How is this different from Unique Paths?

| Aspect | Minimum Path Sum | Unique Paths |
|---|---|---|
| Cell values | Each cell has a cost | All cells cost 1 (or free) |
| Objective | Minimise total cost | Count total paths |
| Transition | min(above, left) + cost | above + left (addition) |
| Answer | dp[m-1][n-1] is a cost | dp[m-1][n-1] is a count |

What are the edge cases?

• 1x1 grid – the answer is the single cell's value.
• Single row – only one path, the sum of all cells.
• Single column – only one path, the sum of all cells.
• All zeros – the minimum path sum is 0.
• Very large values – can overflow int if the grid is large; use long.

// Edge case: 1x1 grid
int[][] single = {{42}};
System.out.println(minimumPathSum(single)); // 42

// Edge case: single row
int[][] row = {{1, 2, 3}};
System.out.println(minimumPathSum(row)); // 6 (only path)

What are common mistakes?

The most common mistake is not initialising the first row and column as prefix sums.

// WRONG: leaving first row/column as grid values
dp[0][0] = fees[0][0];
// dp[0][1] should be dp[0][0] + fees[0][1], not just fees[0][1]
// Because the first row has only one way to arrive: from the left

// CORRECT: prefix sums for edges
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + fees[0][j];

What is the time and space complexity?

Time is O(m * n) because every cell is visited once with O(1) work. Space is O(m * n) for the full table, O(n) with a rolling row, or O(1) if overwriting the input. For a banking routing grid of 1000 x 1000, this runs in milliseconds.

What should a senior engineer know?

A senior engineer should know that this simple DP works only because costs are non-negative and movement is restricted to right and down. If costs could be negative, cycles could reduce the total infinitely, requiring Bellman-Ford. If movement were unrestricted (up, down, left, right), Dijkstra's algorithm would be needed.

They should also know how to reconstruct the actual path by backtracking through the DP table, following the direction (above or left) that contributed the smaller value at each cell.