Dynamic Programming | Set 6 (Min Cost Path) | GeeksforGeeks

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

1) Optimal Substructure
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]“.

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

int minCost(int cost[R][C], int m, int n)

{

     int i, j;

 

     // Instead of following line, we can use int tc[m+1][n+1] or

     // dynamically allocate memoery to save space. The following line is

     // used to keep te program simple and make it working on all compilers.

     int tc[R][C]; 

 

     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];

}

Read full article from Dynamic Programming | Set 6 (Min Cost Path) | GeeksforGeeks