Introduction to Dynamic Programming
What is dynamic programming??
It is an algorithmic paradigm that works by breaking a complex problem into sub-problems and stores the result so as to avoid re-computing it.
Difference from Divide and Conquer:
Divide and conquer is slightly a different technique. In that, we divide the problem in to non-overlapping sub-problems and solve them independently, like in merge sort and quick sort.
When to use DP??
• If the given problem can be broken up in to smaller sub-problems and these smaller sub-problems can in turn be divided in to still-smaller ones, and if in this process, you observe some over-lapping sub-problems, then its a big hint for using Dynamic Programming.
• Overlapping Sub-problems
• Optimal Sub-structure
• Some recursive programs involve solving a problem again and again.
• Instead of solving them again and again we store the results.
Staircase Problem/Fibonacci series
• How many ways are there to climb n steps if you can take 1 or 2 steps at a time??
Memoization- Top Down
n = 10;
"Fibonacci number is %d "
A problem has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.
Consider the problem of finding shortest path between a source and destination node. This problem has following optimal substructure property:
If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v.
The All Pair Shortest Path algorithms like Floyd–Warshall and Bellman–Ford are typical examples of Dynamic Programming.