What is Dynamic Programming?
Dynamic Programming, DP in short, is an intelligent way of solving a special type of complex problems which otherwise would hardly be solved in realistic time frame.
What is that special type of problems?
DP is not best fit for all types of complex problems, it is well suited for the problems with following characteristics only:
A. The given problem must be decomposable in multiple smaller sub problems with similar nature.
B. Sub problems must also be decomposable into still sub problems and this nesting should continue till a stage arises when the current sub problems could be solved with least cost.
C. At any particular stage, the sub problems must be interdependent.
D. At any specific stage the problem could be solved by solving its sub problems.
OK. So this is like Divide and Conquer. Isn't it?
Wait. Don't jump into any conclusion right now. We have not studied the DP procedures yet! we are currently studying the nature of DP problems only. So it will be too early to compare Divide and Conquer with DP.
But this is true, that just a mere look at the characteristics of DP problems gives a feeling that DP is close to Divide and Conquer. But there is a MAJOR difference, in Divide and Conquer, at any stage, the sub problems enjoy NO INTER-DEPENDENCIES.
Let us put this on hold. We will revert back to this topic once more only after we have got some experience in DP. But for the time being, take it from me that DP and Divide & Conquer are not same.
Why do not you say how DP works?
DP works as simple as possible. After the problem is broken down to trivial sub-problems in levels, DP starts solving the sub problems bottom up. Once a sub problem is solved, solution is written down (saved) into a table so that if the same sub problem reappears, we get a ready made solution. This is done in every level.
What is so special about this process?
Yes. It is special. See while you decompose a problems into sub problems, sub problems into sub sub problems and so on, you ultimately reach to a point when you need to solve the same sub problems many a times. And this "many" is not a child's play in real life. Lots of computational resources are unnecessarily spent on this which makes the process sluggish with poor time complexity values.
With DP you can avoid the re computations of the same sub problems.This will save a lot of time and other computational resources. But there are table look ups for solving reappearing sub problems, and this is not going to offer a bed of roses. This will surely take some time, but with hashing and some other smart alternatives, table look ups can be made easy.
Getting out of my head! Show me how DP works with an example.
Lets think of Fibonacci series. We know that Fib(n) = Fib(n-1) + Fib(n-2). Hence to compute Fib(4),
Fib(4) = Fib(3) + Fib(2)
= (Fib(2) + Fib(1)) + Fib(2)
= ((Fib(1) + Fib(0)) + Fib(1)) + Fib(2)
= ((Fib(1) + Fib(0)) + Fib(1)) + (Fib(1) + Fib(0))
This could easily be done with Divide and Conquer with recursion. But there will be several call for the trivial case Fib(1) and Fib(0).
But in DP style we can think that
Fib(4) ------------------- level 0
Fib(3) + Fib(2) ------------------ level 1
Fib(2) + Fib(1)-------------------------- level 2
Fib(1) + Fib(0) -------------------------------- level 3
There will be only two calls of Fib(1) and Fib(0) altogether (shown in violet at level 3). The second Fib(1) (shown in red at level 2) will not be called at all as the result of that is already with us. Similarly Fib(2) (shown in green at level 1) will not be called at all as it has already been computed at level 2. In this way we could avoid re-computations in two occasions.
This is the strength of DP. This strength seems trivial with this trivial example, but as the problem size will grow, this strength will seem to have prominent advantage. Just Think of fib(100)
