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 possible sub-problems.
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 sub-problems.
· An optimum solution for the given problem can be achieved by using result of smaller sub-problem.
· Dynamic algorithms uses Memoization.
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 and 1.
Fibonacci series satisfies the following conditions :
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 fibanocci fib
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 34 55