Dynamic programming

Dynamic programming

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.

Steps to do Dynamic programming

·        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.

Note

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 – An example

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 = Fib_n-1 + Fib_n-2

Hence, a Fibonacci series for the n value 8 can look like this

Fib₈ = 0 1 1 2 3 5 8 13

Fibonacci Iterative Algorithm with Dynamic programming approach

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