What is dynamic programming?

Dynamic programming

Dynamic programming is a way of solving bigger problems with the help of results of sub-problems. Difference between divide and conquer and dynamic programming is that in divide and conquer approach sub problems are mutually exclusive where as in dynamic programming sub problems are overlapping.

Conditions for application of dynamic programming approach

There are two properties which should be fulfilled by any problem to be classified as dynamic programming problem.

First is 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.

Any dynamic programming problem can be solved using recursion, by reducing the candidate each time depending on the required output. However, that solution unnecessary solves already solved sub problems again and again leading to increase time complexity. In dynamic programming approach, we store the results of sub problems and each sub problem is evaluated only once. Hence in DP we trade time with space.

There are many problems which are good candidate for dynamic programming application. I have made a list of such problems and will code there one by one in my following posts.

1.  0-1 knapsack problem
2.  Largest increasing sub sequence
3.  Longest palindrome sub string
4.  Matrix chain multiplication
5.  Longest common sub sequence.
6.  Coin change

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s