Question

Choose a problem that lends to an implementation that uses dynamic programming. Clearly state the problem and then provide high-level pseudocode for the algorithm. Explain why this algorithm can benefit from dynamic programming.

Answer 1

Problem Statement

Calculate the nth term of Fibonacci number.The fibonacci numbers are in the following sequence.

0,1,1,2,3,5,8,13,21,34...

Pseudocode(without dynamic programming)

1. int fib(n){ //function that calculates nth fibonacci number

2. if(n <= 1)

3. return n;

4. else{

5. return fib(n - 1) + fib(n - 2);

6.}

7.}

Pseudocode(dynamic programming)

1.int fib(n); //declaring array dp where fib(i) represents ith fibonacci number.

2.fib(0) = 0,fib(1) = 1 //initializing base conditions

3.for(i = 2 to i = n, i++) do{

4.fib(i) = fib(i - 1) + fib(i - 2);

5.}

Explanation

This algo will use the basic concept of dynamic programming that is memoization and optimal substructure.In the first pseudocode same thing is being calculated over and over again thus increasing the complexity upto   and in dynamic programming implementation we didn't calculate same thing more than once thus complexity reduced to . Therefore dynamic programming implementation is more advantageous.