Dynamic programming approach is similar to divide and conquer.

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

·
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 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_{8} = 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

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

12th Computer Science : Chapter 4 : Algorithmic Strategies : Dynamic programming |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.