Peeling Concept of Dynamic Programming Data-Structures and Algorithm
Dynamic Programming(DP): Dp is a very simple technique but at the same time very difficult to master. The problem is how to identify and solve DP problems.
Another thing just keep in mind that DP and memorization(Means maintaining a table of subproblems already solved) work together. So what is the main difference between the
Divide and Conquer and DP? Divide-Conquer,subproblems are independent whereas in DP the overlap of subproblems occur. This is the main difference.
So now why memoization? because it reduces the exponential complexity to polynomial complexity O(n2), O(n3) for many subproblems.
The major components of DP :
a)Recursion: Solves subproblems recursively.
b)Memorization: Stores already computed values in the table
Dynamic Programming = Recursion + Memorization
So how to identify that this problem will be solved by DP. Keep in mind.
a)Optimal substructure - So an optimal solution to a problem contains the given subproblems.
b)Overlapping subproblems- a recursive solution of subproblems.
So another question can we solve every problem using Dynamic programming?
The answer is no like greedy and divide and conquer not able to solve everything it is that same way. You have to understand one thing the difference between the DP and straightforward recursion is in the memorization of recursive calls.
If subproblems are independent and there is no repetition then memorization does not help so DP is not a solution to such problems.
Dynamic Programming Approaches
to solve any DP problem we have two approaches
1)Bottom-up dynamic programming
2)Top-down dynamic programming
Bottom-up Dynamic Programming :
So here we start with smallest possible input argument value and then slowly increase input argument value and while doing this we store values in a table(memory).
Top-down Dynamic Programming:
So here we broke the problem in subproblems and these subproblems are solved and the solutions remembered in case they need to be solved. Also we save each computed value as a final action of a recursive function and at the same, we also check if pre-computed values exist.
Algorithms of Dynamic Programming :
These are a few algorithms of DP.
1)String Algorithms include the longest common subsequence, longest increasing subsequence, longest common substring, edit distance.
2)Bellman-Ford Algorithm, Floyd's All pair shortest path algorithm.
3)Chain Matrix multiplication
4)Subset Sum
5)0/1 Knapsack
6)Travelling salesman problem
Let's understand the Dynamic Programming in more depth:
Fibonacci Series(Current number is the sum of two previous number).Remember it.
Fib(n) = 0 for n =0
Fib(1) = 1 for n=1
= Fib(n-1) + Fib(n-2) ........ for n > 1
So now think of its recursive solution which is very simple.
int RecursiveFibonacci(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
}
Above we discuss about Memorization So how Memorization helps here?
Ans: It helps like it produces a call tree that calls the function on the same value many times.
Fib(5)
Fib(4) + Fib(3)
(Fib(3) + Fib(2)) + (Fib(2) + Fib(1))
...............
(((Fib(1) + Fib(0)) + Fib(1)) + (Fib(1) + Fib(0) + Fib(0))) + Fib(0) + Fib(1))
So here Fib(2) was calculated 3 times(overlapping of subproblems) this leads to an exponential time. Instead of solving the same subproblems again and again just keep track of it store the previously calculated values then it reduces the complexity.
Bottom-up Approach:
int fib[n];
int fib(int n)
{
if(n==0 || n==1)
retun 1
fib[0] =1;
fib[1] =1;
for(int i =2 ; i<n; i++)
{
fib[i] = fib[i -1] + fib[i-2]
}
return fib[n -1]
}
Top-down Approach :
int fib[n];
int fibonacci(int n)
{
if(n==1) retun 1;
if(n==2) retun 1;
if(fib[n]!=0)
{
return fib[n];
}
return fib[n] = fibonacci(n -1) + fibonacci(n -2);
}
So both of them reduces the problem of complexity to O(n) this is because if a value is already computed then we are not calling the subproblems again. We are directly taking it from
table.
Time Complexity O(n)
Space Complexity: O(n) for table.
We can further improve the space complexity by O(1)
So the question is How?
Ans: So just think about Fibonacci series is basically the current value is the sum of two previous calculations only. So we do not have to store all the previous values right? we just have two store last two values we can calculate the current value.
