# What is Dynamic programming?

## Conditions for application of dynamic programming approach

**optimal structure**. Problem should ask for the optimal value as result like maximum value for given weight, over maximum no of applications with given bandwidth etc and optimal solution of subproblems can be used to get optimal solution of bigger problem. Second, there should be

**overlapping sub problems,**which can be used to derive the solution for the bigger problem.

**There are two approaches in which dynamic programming can be used :**

1. Bottom up approach

In this, problem is divided into smaller problems and then smallest problem is solved and used upward to solve bigger problems.

2. Top down approach

When we have recursive relation like this T(n) = 2 T(n-1) + n, where subproblem is not significantly smaller than the original problem, and going down the recursion tree, many subproblems are same, it is better to store results of each problem we have seen till now and use them to calculate solution of subproblems, here subproblems already calculated are not again done. This technique is called as memoization.

1. 0-1 knapsack problem

2. Longest increasing subsequence

3. Longest palindrome sub string

4. Matrix chain multiplication

5. Longest common sub sequence.

6. Coin change

Pingback: Count all possible paths in maze or grid – Algorithms and Me()

Pingback: Find Minimum Cost Path in a 2D Matrix: DP – Algorithms and Me()