What is 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. Longest increasing subsequence
3. Longest palindrome sub string
4. Matrix chain multiplication
5. Longest common sub sequence.
6. Coin change