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-
[cpp]
//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) );
}
[/cpp]
Efficient Code-
[cpp]
//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];
}
[/cpp]
Time Complexity of the DP implementation is O(mn) which is much better than Naive Recursive implementation.
