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