**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.