DAA Answers 9 - Dynamic programming

DAA-Q59 Dynamic programming

Break a complex problem into subproblems, solve each once, store results. Needs overlapping subproblems and optimal substructure. Top-down (memoization) or bottom-up (tabulation). Steps: characterise, define recursively, compute bottom-up, construct the solution.

DAA-Q60 Divide & conquer vs DP

D&C: recursive, top-down, independent subproblems, repeated work (merge sort). DP: bottom-up, overlapping subproblems, table, each solved once (Fibonacci, matrix chain, LCS).

DAA-Q61 Fibonacci with and without DP

F(n)=F(n-1)+F(n-2). Naive recursion O(2^n); memoization/tabulation O(n).

DAA-Q62 Matrix chain multiplication; p={4,10,3,12,20,7}

m[i,j]=min over k of m[i,k]+m[k+1,j]+p(i-1)p(k)p(j). Diagonal fill: m[1,2]=120, m[2,3]=360, m[3,4]=720, m[4,5]=1680, m[1,3]=264, m[2,4]=1320, m[3,5]=1140, m[1,4]=1080, m[2,5]=1350, m[1,5]=1344. O(n^3).

DAA-Q63 Longest common subsequence

A subsequence deletes elements without reordering. If xm=yn then c[i,j]=c[i-1,j-1]+1; else max(c[i-1,j],c[i,j-1]); 0 if i=0 or j=0. O(mn) time and space.