Dynamic Programming - Introduction
December 21, 2017
Have you ever heard of the term
dynamic programming and thought that this is a really tricky programming method, then you are absolutely wrong.
In fact, it is a combination of multiple programming techniques. As the name suggests, the term dynamic denotes an effective and efficient way of solving a problem.
In simple words, dynamic programming is dividing a task into subtasks and then solving the subtasks such that each unique subtask is solved only once, thus optimizing the efficiency of the algorithm.
Prerequisites to solving dynamic problems
A problem can be solved with dynamic programming if the problem has:
1. Optimal substructure
2. Overlapping Subproblems
Optimal Substructure
Don't get confused with the term. In fact, a problem is said to have an optimal substructure if it can be represented in the form of recursion, with some base values that have a trivial value.
Code to find the nth Fibonacci number using pure recursion:
int fibonacci (int n) {
if (n < 2)
return 1;
return fibonacci(n-1) + fibonacci (n-2);
}
The above method is said to have an optimal substructure as it's using recursion to find the nth Fibonacci number and the base values exist for n<2.
Overlapping Sub-problems
If the problem is divided into subproblems such that two or more individual subproblems are identical, in other words, the solution of these subproblems is same. Hence, they are said to be the overlapping subproblems as there is no need to solve these problems, again and again, instead the result of solving one subproblem can be used to find the result of identical subproblem.
For the above code, the pictorial representation can be given as:
For the above code, the pictorial representation can be given as:
(Image source: Google)
As you can see, the two grey parts are identical. In the above code, the same subproblem is solved twice. Dynamic programming provides different approaches to handle such cases.
Approaches to dynamic programming
There are two approaches defined to solve a problem with dynamic programming:
1. Memoization (Top-down approach)
2. Tabulation (Bottom Up approach)
2. Tabulation (Bottom Up approach)
The aim behind both the approaches is to store the results of subproblems so that we do not have to recompute the same subproblem again.
Memoization
It is the process of dividing the problem into subproblems until we arrive at the base values and then computing the results of the subproblems in a top-down manner. A benefit of this approach is that we need not compute those subproblems whose results we do not require in the computation of the problem.
In the above problem, using memoization, we move down the tree dividing it into subproblems and calculating the values and storing their results in a memo. The green colors denote that we need to compute these values. Red colors denote that we reused the values that we have already computed. Yellow colors denote that we didn't have to compute these values as their parent problem has already been computed.
So the actual tree would look something like this.
Tabulation
It is the process of solving all the subproblems starting with the base values until we reach the desired solution in a bottom-up manner. In this approach, we need to compute all the subproblems, to arrive at the desired solution, even the ones whose result was never needed in solving the problems, this making extra computation, even if it is not required. Although this approach does not look good but, trust me, in many cases this can be helpful.
Consider the above problem, if need to compute nth Fibonacci number such that n is a larger number like 40 or 50, tabulation can prove to be even more efficient. Memoization could be a costlier approach for that case. However, it all depends on the scenario and the preconditions of a problem.
void fib (n){
f[0] = 0;
f[1] = 1;
for(int i=2;i<=n;i++){
fib[i] = fib[i-1] + fib[i-2];
}
}FYI, To compute the 50th Fibonacci number, the following are the time taken by a computer:
Pure Recursion: 11 seconds
Memoization: 0.34 seconds
Tabulation: 0.14 seconds
Thanks for the read...
Stay Tuned :-)
0 comments