Dynamic Programming - Min Cost Path

Dynamic Programming - Min Cost Path

Given a cost matrix cost[][] and a position (m, n) in cost[][],
write a function that returns cost of minimum cost path to reach (m, n) from (0, 0).

 Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

 The path to reach (m, n) must be through one of the 3 cells:
 (m-1, n-1) or (m-1, n) or (m, n-1).

 So minimum cost to reach (m, n) can be written as “minimum of the 3 cells plus cost[m][n]”.

Solution: 

minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MinCostPathApp
{
private static int min(int x, int y, int z)
{
       if (x < y)
           return (x < z)? x : z;
       else
           return (y < z)? y : z;
 }

private static int minCost(int cost[][], int m, int n)
{
       int i, j;
       int tc[][]=new int[m+1][n+1];

       tc[0][0] = cost[0][0];

       /* Initialize first column of total cost(tc) array */
       for (i = 1; i <= m; i++)
           tc[i][0] = tc[i-1][0] + cost[i][0];

       /* Initialize first row of tc array */
       for (j = 1; j <= n; j++)
           tc[0][j] = tc[0][j-1] + cost[0][j];

       /* Construct rest of the tc array */
       for (i = 1; i <= m; i++)
           for (j = 1; j <= n; j++)
               tc[i][j] = min(tc[i-1][j-1],
                              tc[i-1][j],
                              tc[i][j-1]) + cost[i][j];

       return tc[m][n];
   }

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

}

Output: minimum cost to reach (2,2) == 8

Time Complexity: O(mn) which is much better than Naive Recursive implementation.