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.
has 2 ways to construct the lookup table:
Memoization - Constructs lookup table on demand
Tabulation - Constructs lookup table from bottom-up, considering all
of fibonacci series (one with naive recursive solution)?
need to consider how many computations are required to compute F(n)?
it's the sum of computations required to compute F(n-1) and F(n-2)
if C(n) is the computations required to compute C(n)
C(n) = C(n-1) + C(n-2) which is again a fibonacci series.
we assume that C(n) is exponential, then
where a is some constant.
= 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
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
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)