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. Memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of previous function calls and returning the cached result when the same inputs occur again.
Note 12th Computer Chapter - - . . Fibonacci Series – An example Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − Fib & Fib .
The initial values of Fib & Fib can be taken as and . Fibonacci series satisfies the following conditions : Fibn = Fib n- + Fib n- Hence, a Fibonacci series for the n value can look like this Fib = . . Fibonacci Iterative Algorithm with Dynamic programming approach The following example shows a simple Dynamic programming approach for the generation of Fibonacci series.
Initialize f0= , f1 = step- : Print the initial values of Fibonacci f0 and f1 step- : Calculate fibanocci fib ← f0 + f1 step- : Assign f0← f1, f1← fib step- : Print the next consecutive value of fibanocci fib step- : Goto step- and repeat until the specified number of