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 divideandconquer problems.
Example: In a fibonacci series (defined by f(n) = f(n1) + f(n2) 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 bottomup, 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(n1) and F(n2)
So,
if C(n) is the computations required to compute C(n)
Then
C(n) = C(n1) + C(n2) which is again a fibonacci series.
If
we assume that C(n) is exponential, then
C(n)
= a^{n}
where a is some constant.
a^{n}
= a^{n1}
+ a^{n2}
Dividing
by a^{n2},
a^{2}
= 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.62^{n})
Solution for a Quadratic Equation
To
refresh some highschool 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) = (a^{n}  b^{n})/√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 = (√51)/2)
