Minimum Cost Path in a Grid

Given a grid of non-negative costs and a target cell (m, n), find the minimum total cost of a path from (0, 0) to (m, n). From a cell you can move right, down, or diagonally down-right. The cost of a path is the sum of all the cells on it, including both ends.

Example

Text

grid:        target (2, 2)
1 2 3
4 8 2        Output: 8   (1 -> 2 -> 2 -> 3: (0,0) -> (0,1) -> (1,2) -> (2,2))
1 5 3

Brute force: try every path

The cheapest way to reach (i, j) is its own cost plus the cheapest way to reach one of the three cells that can move into it: (i - 1, j), (i, j - 1), or (i - 1, j - 1).

Java

public class Main {
    static int minCost(int[][] grid, int i, int j) {
        int here = grid[i][j];
        if (i == 0 && j == 0) return here;
        if (i == 0) return here + minCost(grid, 0, j - 1);
        if (j == 0) return here + minCost(grid, i - 1, 0);
        return here + Math.min(minCost(grid, i - 1, j),
                      Math.min(minCost(grid, i, j - 1), minCost(grid, i - 1, j - 1)));
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 2, 3}, {4, 8, 2}, {1, 5, 3}};
        System.out.println(minCost(grid, 2, 2));
    }
}

Output

Time: O(3^(m+n)): each call makes three more, and the same cells are recomputed along many paths. Space: O(m + n) for the recursion.

Optimal: fill a table

There are only (m + 1)(n + 1) distinct cells, so compute each cell's cheapest cost once, row by row. All three predecessors of a cell come earlier in that order. The first row and first column can only be reached one way.

	col 0	col 1	col 2
row 0	1	3	6
row 1	5	9	5
row 2	6	10	8

Java

public class Main {
    static int minCost(int[][] grid, int m, int n) {
        int[][] cost = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                int bestBefore;
                if (i == 0 && j == 0) bestBefore = 0;
                else if (i == 0) bestBefore = cost[0][j - 1];
                else if (j == 0) bestBefore = cost[i - 1][0];
                else bestBefore = Math.min(cost[i - 1][j], Math.min(cost[i][j - 1], cost[i - 1][j - 1]));
                cost[i][j] = grid[i][j] + bestBefore;
            }
        }
        return cost[m][n];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 2, 3}, {4, 8, 2}, {1, 5, 3}};
        System.out.println(minCost(grid, 2, 2) + " " + minCost(grid, 1, 1));
    }
}

Output

8 9

Time: O(m·n). Space: O(m·n); keeping only the previous row brings it to O(n).

Edge cases

Target (0, 0): that cell's cost alone.
Single row or column: one possible path, the running sum.
Only right and down moves (LeetCode 64): drop the diagonal term.