In Divide an Conquer algorithms we use independent operations on sub-parts of a program , and we only store the final result, but in dynamic programming, the operation on one sub-part of the program depend on each other. In dynamic programming, we usually store the result of all the different sub-programs so we could use it later in the program. Instead of recursion Dynamic programming approach iteration tools such as loop, so the exponential complexity of recursions statements can be reduced by linear complexity of iterations. We use Dynamic Programming to solve those problems which can be solved by divide and Conquer algorithms but instead of using recursion we use iteration so we can reduce the time complexity. In Dynamic Programming, we store all the sub-program result so we can compare all to get the optimized result.
Comparison of Dynamic Programming with Greedy and Divide and Conquer algorithm
In Greedy Algorithms, we go for the local optimization where in dynamic algorithms our approach is for overall optimization of the problem. In divide and Conquer all the sub-part of program merge to get the overall solution, in dynamic all the sub-programs result combination give the overall result.
Some application of Dynamic Programming
- Fibonacci number series
- Knapsack problem
- Tower of Hanoi
- All pair shortest path by Floyd-Warshall
- Shortest path by Dijkstra
- Project scheduling
People are also reading: