Minimum Cost Path (DP Example)

Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems and optimal substructure.When applicable,the method takes far less time than naive methods that don’t take advantage of the sub-problem overlap.

A problem is said to have overlapping sub-problems if the problem can be broken down into sub-problems which are reused several times or a recursive algorithm for the problem solves the same sub-problem over and over rather than always generating new sub-problem.

A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its sub-problems.

Example of dynamic programming-

Given a cost matrix cost[][] having m rows and n columns,the task is to find the cost of minimum cost path to reach (m-1,n-1) from (0,0).Each cell of the matrix represents a cost to traverse through that cell. 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.

Example-

Cost matrix-

1 2 3
4 8 2
1 5 3

The minimum cost path is (0,0)–>(0,1)–>(1,2)–>(2,2). The cost of the path is 8 (1 + 2 + 2 + 3).

Recursive Code-

//mcost(m-1,n-1) is called.
//cost[][] is the cost matrix
int mcost(int a,int b)
{
   if (b < 0 || a < 0)
      return INT_MAX;
//base condition
   else if (a == 0 && b == 0)
      return cost[a][b];
   else
      return cost[a][b] + min( mcost(a-1,b-1),mcost(a-1,b),mcost(a,b-1) );
}

Efficient Code-

//mcost(m-1,n-1) is called.
//temp[][] is used for storing the results which need to be calculated again & again.
int mcost(int a,int b)
{
     int i, j;

     int temp[R][C]; 
 
     temp[0][0] = cost[0][0];
 
//initializing first column
//a cell in first column can be traversed only from cell just above it.
     for (i = 1; i <= a; i++)
        temp[i][0] = temp[i-1][0] + cost[i][0];
 
//initializing first row
//a cell in first row can be traversed only from cell just left to it.    
     for (j = 1; j <= b; j++)
        temp[0][j] = temp[0][j-1] + cost[0][j];

//constructing rest of the array
     for (i = 1; i <= a; i++)
{
     for (j = 1; j <= b; j++)
{
   temp[i][j] = min(temp[i-1][j-1], temp[i-1][j], temp[i][j-1]) + cost[i][j];
}
}
     return temp[a][b];
}

Time Complexity of the DP implementation is O(mn) which is much better than Naive Recursive implementation.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,085 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>