Dynamic programming is an algorithmic design
method that can be used when the solution to a problem can be viewed as the
result of a sequence of decisions. Dynamic programming approach is similar to
divide and conquer. The given problem is divided into smaller and yet smaller
Dynamic programming is used whenever problems
can be divided into similar sub-problems. so that their results can be re-used
to complete the process. Dynamic programming approaches are used to find the
solution in optimized way. For every inner sub problem, dynamic algorithm will
try to check the results of the previously solved sub-problems. The solutions
of overlapped sub-problems are combined in order to get the better solution.
The given problem will be divided into smaller overlapping
An optimum solution for the given problem can be achieved by using
result of smaller sub-problem.
Dynamic algorithms uses Memoization.
or memoisation is an optimization technique used primarily to speed up computer
programs by storing the results of expensive function calls and returning the
cached result when the same inputs occur again.
Fibonacci series generates the subsequent
number by adding two previous numbers. Fibonacci series starts from two numbers
− Fib 0 & Fib 1. The initial values of Fib 0 & Fib 1 can be taken as 0
Fibonacci series satisfies the following
Fibn = Fibn-1 + Fibn-2
Hence, a Fibonacci series for the n value 8 can
look like this
Fib8 = 0 1 1 2 3 5 8 13
The following example shows a simple Dynamic
programming approach for the generation of Fibonacci series.
Initialize f0=0, f1 =1
step-1: Print the initial values of Fibonacci
f0 and f1
step-2: Calculate fibanocci fib ← f0 + f1
step-3: Assign f0← f1, f1← fib
step-4: Print the next consecutive value of
step-5: Goto step-2 and repeat until the
specified number of terms generated
For example if we generate fibobnacci series
upto 10 digits, the algorithm will generate the series as shown below:
The Fibonacci series is : 0 1 1 2 3 5 8 13 21