Make delicious recipes!

Dynamic Programming


Layman's Definition: Dynamic programming is a class of problems where it is possible to store results for recurring
computations in some lookup so that they can be used when required again by other computations.

This improves performance at the cost of memory.

DP can be applied to improve backtracking as well as divide-and-conquer problems.

Example: In a fibonacci series (defined by f(n) = f(n-1) + f(n-2) series), the function for
all lower values of ‘n’ is calculated again and again if done naively by recursion.

If we store all values of f(n) in an array, then the recursive calls will turn into lookups and performance will be greatly improved.


DP has 2 ways to construct the lookup table:

1) Memoization - Constructs lookup table on demand

2) Tabulation - Constructs lookup table from bottom-up, considering all the cases.


Order of fibonacci series (one with naive recursive solution)?


We need to consider how many computations are required to compute F(n)?

Clearly it's the sum of computations required to compute F(n-1) and F(n-2)

So, if C(n) is the computations required to compute C(n)

Then C(n) = C(n-1) + C(n-2) which is again a fibonacci series.


If we assume that C(n) is exponential, then

C(n) = an where a is some constant.


an = an-1 + an-2

Dividing by an-2,

a2 = a + 1


Solutions for this quadratic equation are:

First of these values is also known as Golden Ratio as it has tremendous other properties in all walks of life.


Since negative power would not make sense in the above equation, we ignore it.
Hence the order of Fibonacci series comes out to be O(1.62n)


Solution for a Quadratic Equation

To refresh some high-school maths (and to take a virtual break from algorithms), let us see how the 2 roots of a quadratic equation can be derived:


O(1) solution for Fibonacci Series


Above equation for Q and D can be solved as Eigenvalues and Eigenlines to give:

F(n) = (an - bn)/√5 where:

a = (1+√5)/2 and

b = (1-√5)/2

This is a constant order solution!! Here is a proof of its correctness:
(Here Phi = (1+√5)/2 and phi = -b = (√5-1)/2)






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal