It is considered as a careful bruteforce. And interestingly we will get it in polynomial time.What it does is divide the problem into sub problem and solve the same and reuse the same for larger problem.
Lets take the example of fibonacci number !!
F(n) :
if(n <= 2) :
f = 1;
else :
f = f(n-1)+f(n-2);
return f;
|
Looks like neat !! But it is not because it running in an exponential time, because each time recalculating many functions.
Eg : F(4) :
f = [ F(3) + F(2) ]
= [ F(2) + F(1) ] + 1
= [ 1 + 1 ] + 1
= 2 +1
= 3
Here we can see that F[2] is calculated 2 times. Like that there may be many situations where we are recalculating.
Proof exponential time :
T(n) = T(n-1) + T(n-2)+ O(1)
> 2T(n-2)
= O(2^(n/2))
Memorization
In this case we are adding an extra dictionary for storing all the already found values, if it is there we will just return that else we will calculate the same and put in the dictionary.
F(n) :
memo = {}
if n in memo:
return memo[n]
if n <= 2 :
f = n
else :
f = F(n-1)+F(n-2)
memo[n] = f
return f
|
DP = recursion + memorization
Time taken = Number of subproblem * time/subproblem
Ok...lets nail it,
F(n) :
fib = {}
for k in range(1,n+1):
if k <= 2:
f = 1
else :
f = fib[n-1] + fib[n-2]
fib[k] = f
return fib[n]
|
This is fibonacci in DP. Here each time it is reusing already calculated values because it is working in bottom up fashion. You can see that in the for loop. we have completely replaced the recursion with a for loop. Here you can see the problem is running in O(n) where n is the number of subproblem to the main problem.
Shortest path algorithm and text justification in DP style
This can be done in DP : watch https://www.youtube.com/watch?v=ENyox7kNKeY
Climbing the step problem
Consider there is a staircase having 98 steps and find out the number of ways you can climb the staircase.
Number of ways i can go to step 2
- 1 - 2
- 2
Number of ways i can get to step 3
- 1 - 2 - 3
- 1 - 3
- 2 - 3
Number of ways i can get to step 4
- 1 - 2 - (4)
- 2 - (4)
- 1 - 2 - 3 - (4)
- 1 - 3 - (4)
- 2 - 3 - (4)
If you see all the possible outcomes of the ways to get to step 4 is either,
- 2 steps from step 2
or
- 1 step from step 3
So number of ways to step 4 = number of ways to step 3 + number of ways to 2
So F(4) = F(3) + F(2)
F(n) = F(n-1) + F(n-2)
|
If you see it is nothing but fibonacci series only. And if we do it from bottom up then we can solve this problem
Maximum SubArray problem
Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.
Read more here : http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
The easiest way to find the maximum subarray is dynamic programming, because you can easily relate each element to it’s previous element, so that we can easily create the formula for the same as :
DP[ i ] = Max( Input[ i ] , Input[ i ] + DP[ i-1 ] )
|
It says nothing but to assign maximum of
- current input
- current input + max value of ( i-1 )th position
The output of the above will be
Maximum possible value :6
Maximum subarray is : 1 2 -1 4 (reverse order)
Longest Increasing sequence
Read here :
In recursive call :
output ::
max :6
maxList :[10, 22, 33, 50, 60, 80]
In Dynamic programming way :
No comments:
Post a Comment