# Dynamic Programming Study Notes

By Mukesh Kumar|Updated : August 13th, 2021

## Dynamic Programming

Dynamic programming helps to solve a complex problem by breaking it down into a collection of simpler subproblems, solving each of those sub-problems just once, and storing their solutions.

A dynamic programming algorithm will examine the previously solved sub problems and will combine their solutions to give the best solution for the given problem.

It is used when the solution can be recursively described in terms of solutions to subproblems (optimal substructure).

• Optimal substructure: optimal solution to problem consists of optimal solutions to subproblems.
• Overlapping subproblems: few subproblems in total, many recurring instances of each.
• Solve bottom-up, building a table of solved subproblems that are used to solve larger ones.

## Dynamic Programming

Dynamic programming helps to solve a complex problem by breaking it down into a collection of simpler subproblems, solving each of those sub-problems just once, and storing their solutions.

A dynamic programming algorithm will examine the previously solved sub problems and will combine their solutions to give the best solution for the given problem.

It is used when the solution can be recursively described in terms of solutions to subproblems (optimal substructure).

• Optimal substructure: optimal solution to problem consists of optimal solutions to subproblems.
• Overlapping subproblems: few subproblems in total, many recurring instances of each.
• Solve bottom-up, building a table of solved subproblems that are used to solve larger ones.

### Dynamic Programming Algorithms

• Fibonacci sequence
• 0-1 knapsack problem
• Longest Common Subsequence problem
• Matrix chain multiplication
• All pairs shortest path problem
• Subset-sum problem
• Optimal Binary Search Tree

## Fibonacci Sequence:

The Fibonacci numbers are the numbers in the following sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

F(0) and F(1) are 0 and 1 respectively, and each other subsequent number is the sum of the previous two such that the recurrence relation is F(n) = F(n-1) + F(n-2).

Recursive Program

ALGORITHM Rec_Fib(n)

{

if (n==0)

return 0;

else if(n==1)

return 1;

else

return

{

Rec_Fib(n-1) + Rec_Fib(n-2)

};

}

Time Complexity

Assume without using Dynamic Programming (or say Memorization), for each recursive step two recursive function calls will be done, that means the time complexity is exponential to n, so the time complexity is O(2n).

Note that some results will be used repetitively, just imagine if it is computed in iterative way, then the time complexity should be in linear time, recursion with memorization (dynamic programming) helps to do the similar thing, so the time complexity can be reduced to O(n)

## Knapsack Problem (0-1 knapsack)

0/1 Knapsack problem can be solved using dynamic programming.

Let 'n' be the number of objects and 'm' be the capacity of Knapsack.

Recursive Program

KS(m,n)

{

if(m==0||n==0)

return 0;

if(Wn>m)

return (KS(m,n-1));

else

{

x=KS(m,n-1);

y=KS(m-Wn,n-1) + Pn;

z=max(x, y);

return z;

}

}

Time Complexity

Upon executing the above code , the upper bound will be n level complete binary tree which has 2n nodes.

Hence time complexity = O(2n)

But there are many repeated function calls  , so storing the values of repeated functions in a table, distinct function calls = m*n

So, time complexity = O(mn)

## Matrix Chain Multiplication:

To multiply matrices , more than one order is possible . So the number of multiplications differ in different cases.

Example :

A(3 × 4)     B(4 × 5)       C(5 × 3)

D = ABC , find minimum number of multiplications.

Now two orders are possible to multiply:

A(BC) and (AB)C

Order 1 : A(BC)

Multiplications for BC = 4 × 5 × 3 = 60

Multiplications for A × (upper result) = 3 × 4 × 3 = 36

Total = 96

Order 1 : (AB)C

Multiplications for AB= 3 × 4 × 5=60

Multiplications for (upper result) × C = 3 × 5 × 3 = 45

Total = 105

Hence the minimal number of multiplications are = 96

Time Complexity

To multiply the matrices in order to get minimum multiplications, the number of functions calls = n!

But if we store and re-use the values of repeated function, then number of distinct function calls = n2

Hence Time Complexity = O(n2)

## Longest Common Sub-sequence :

Sub-sequence  : Longest common sub-sequence of a given sequence is just the given sub-sequence only in which 0 or more symbols left out.

Example :

Sequence = (ABBABB)

Sub-sequence 1 = (BBABB)

Sub-sequence 2 = (ABBABB)

Sub-sequence 3 = (BB)

Sub-sequence 4 = (B)

Longest Sub-sequence : Z is a common sub-sequence of two sequences X and Y if Z is a sub-sequence to both X and Y.

Example :

X = (ABBABB)

Y = (BAABAA)

Common Sub-sequence 1 = (AA)

Common Sub-sequence 2 = ()

Common Sub-sequence 3 = (ABA)    <------ Longest Common Sub-sequence

Common Sub-sequence 4 = (BA)

Recursive Program :

LCS(m,n)

{

if(m==0||n==0)

return 0;

else

if(x[m]==y[n])

return (1+LCS(m-1,n-1));

else

{

a=LCS(m,n-1);

b=LCS(m-1,n);

c=max(a,b);

return c;

}

}

Time Complexity :

LCS(m,n) will generate (m+n) level complete Binary Tree.

Hence time complexity = O(2(m+n))

But if we store and re-use the values of repeated function , then number of distinct function calls = mn

Hence, Time Complexity = O(mn)

## Sum of Subsets

Input : An array of n-elements and integer m

Output : Find subset whose sum is m

Example :

A = (50,20,40,60,80,70,10,30)

m=100

The possible subsets are :

S1 = (50,40,10)

S2 = (50,20,30)

S3 = (40,60)

To find these subsets we have to make n-level complete binary tree which will comprise of all the possible cases.

Time Complexity :

As n level complete binary tree is generated , so number of function calls = 2n

But if we store and re-use the values of repeated function , then number of distinct function calls = mn

Hence, Time Complexity = O(mn)

## All Pairs Shortest Path

For finding all pairs shortest path , FLOYD WARSHALL ALGORITHM is used whose time complexity is O(n3).

So that's all about dynamic programming.

You can follow the detailed champion study plan for GATE CS 2022 from the following link:

Detailed GATE CSE 2022 Champion Study Plan

Candidates can also practice 112+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link: GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com