Min Cost Path Problem

The problem, simply

You get a grid cost with m rows and n columns. Each square has a price. You start on the top left square and must reach the bottom right square. From any square you may step right, down, or diagonally down-right.

You pay for every square you stand on, including the first and the last. Give back the smallest total you can pay.

A story to remember it

Picture it

Examples

Way 1: the simple way

Ask the question backwards. The cheapest way to reach square (i, j) is its own price plus the cheapest way to reach one of the three squares that lead into it.

1. best(0, 0) = cost[0][0].
2. Squares outside the grid cost "infinity", so they are never chosen.
3. best(i, j) = cost[i][j] + min(best(i-1, j), best(i, j-1), best(i-1, j-1)).

class Solution {
    public int minCost(int[][] cost) {
        return best(cost, cost.length - 1, cost[0].length - 1);
    }

    private int best(int[][] cost, int i, int j) {
        if (i < 0 || j < 0) return Integer.MAX_VALUE;      // off the grid, never pick it
        if (i == 0 && j == 0) return cost[0][0];           // the start square
        int up = best(cost, i - 1, j);
        int left = best(cost, i, j - 1);
        int diag = best(cost, i - 1, j - 1);
        return cost[i][j] + Math.min(up, Math.min(left, diag));
    }
}

How long it takes: three branches per call and up to m + n levels, O(3^(m+n)). Extra room: the waiting calls, O(m + n). The MAX_VALUE never gets added to, because every square except the start has at least one neighbor inside the grid.

Way 2: the clever way

Fill a table dp the same size as the grid, row by row, left to right. When you reach a square, the three squares it needs are already filled.

1. dp[0][0] = cost[0][0].
2. Top row: only from the left. Left column: only from above.
3. Every other square: dp[i][j] = cost[i][j] + min(up, left, up-left).
4. The answer is dp[m-1][n-1].

In the animation, the left grid shows the prices and the right grid is the table. Arrows point from the squares each answer reads. The brighter arrow source is the cheapest one.

class Solution {
    public int minCost(int[][] cost) {
        int m = cost.length, n = cost[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = cost[0][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + cost[0][j];   // top row: from the left
        for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + cost[i][0];   // left column: from above
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int cheapest = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                dp[i][j] = cost[i][j] + cheapest;
            }
        }
        return dp[m - 1][n - 1];
    }
}

How long it takes: each square once, three looks each, O(m * n). Extra room: the table, O(m * n). You can keep only one row, or write the answers into the cost grid itself if you are allowed to change it, for O(n) or O(1).

Watch out for

• Do not forget the price of the start square. The answer includes it.
• Read the moves carefully. LeetCode 64 allows only right and down. This version also allows down-right.
• Greedy (always step to the cheapest next square) fails. A cheap step can lead into an expensive corner.

What interviewers ask next

• Print the path. Walk back from the end, each time to the neighbor with the smallest dp value.
• What if you may also move up and left? Then squares can depend on each other in circles, so a table filled in one order does not work. Use Dijkstra's shortest path with a heap.
• Count how many cheapest paths there are. Keep a second table of counts and add the counts of every neighbor that ties for the minimum.
• What if some squares are walls? Treat them as infinity in the table.

Remember this

Grown-up words: the stones are cells of a matrix, the number written on each stone is the DP state, the three neighbors are the transitions, and the repeated questions in the recursion are overlapping subproblems.