Scribd
Upload
2 views

LEC 14 Dynamic Programming

Uploaded by

shwetarana155
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views

LEC 14 Dynamic Programming

Uploaded by

shwetarana155
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 24

Dynamic Programming

Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
• DP is like divide and conquer approach in which problem is divide into
sub problem and sub problem further divided into sub sub problem
and so on until we got smallest problem.
• In DP sub problems are related.
• It gives guarantee of optimal solution.

CS_GATE@ANKUSH_SAKLECHA 10
Dynamic Programming

CS_GATE@ANKUSH_SAKLECHA 11
Dynamic Programming
Problems that can solve using Dynamic Programming :

1. longest common subsequence


2. Matrix chain multiplication
3. 0/1 kanpsack problem
4. Optimal Binary Search tree
5. Traveling salesmen person problem
6. All pair shortest path problem
7. Sum of subset problem
8. Bellman ford algorithm

CS_GATE@ANKUSH_SAKLECHA 12
Dynamic Programming

1. longest common subsequence

CS_GATE@ANKUSH_SAKLECHA 13
Dynamic Programming
1. Longest common subsequence :
X=abbaabbc
Y=abaabbcb
C[i][j] = 0 if i =0 or j = 0
C[i][j] = max(c[i-1,j], c(i,j-1)) if xi ≠ yj Complexity = ?
C[i][j] = C[i-1,j-1] + 1 if xi = yj
X=abcbcba
Y=bcbbcbb
yi\xi 0 a b c b c b a
0 0 0 0 0 0 0 0 0
b 0 0
c 0
b 0
b 0
c 0
b 0
b 0

CS_GATE@ANKUSH_SAKLECHA 14
Dynamic Programming
1. Longest common subsequence :
X=abbaabbc
Y=abaabbcb
C[i][j] = 0 if i =0 or j = 0
C[i][j] = max(c[i-1,j], c(i,j-1)) if xi ≠ yj Complexity = ?
C[i][j] = C[i-1,j-1] + 1 if xi = yj
X=abcbcba
Y=bcbbcbb
yi\xi 0 a b c b c b a
0 0 0 0 0 0 0 0 0
b 0 0
c 0
b 0
b 0
c 0
b 0
b 0

CS_GATE@ANKUSH_SAKLECHA 15
Dynamic Programming
Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not
necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and
B. Then x + 10y = ___.
(A) 33
(B) 23
(C) 43
(D) 34
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming
Dynamic Programming

You might also like