Question

Explain the concept of Dynamic programming with suitable examples.

Answer 1

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. The dynamic programming approach is similar to divide and conquer. The given problem is divided into smaller and yet smaller possible subproblems.

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 an optimized way. For every inner subproblem, the dynamic algorithm will try to check the results of the previously solved sub-problems. The solutions of overlapped subproblems are combined in order to get a better solution.

Steps to do Dynamic programming:

1. The given problem will be divided into smaller overlapping sub-problems.
2. An optimum solution for the given problem can be achieved by using the result of a smaller subproblem.
3. Dynamic algorithms use Memoization.

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 he 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 the 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 Fibonacci fib
step – 5: Go to step – 2 and repeat until the specified number of terms generated
For example, if we generate Fibonacci series up to 10 digits, the algorithm will generate the series as shown below:
The Fibonacci series is: 0 1 1 2 3 5 8 1 3 2 1 3 4 5 5