Find the least operation to get the The structure of an optimal a Direct divide and conquer method, one get the a If a parenthesis is an optimal one then its sub parenthesis is optimal for the su Pm)=∑Pk)(n-k) a Catalan number grows as? (4/n 2 A recursive solution Computing the optimal costs m[i,jI 0 if i=j n小 minmei. 1+mik+1 /1+P-PP, if i<j 437525003500 清华太学未证想 A2 A3 A4 A5A6 Constructing an optimal solution Elements of dynamic programming ■S[』 records the values of k such that the optimal a Two important points enthesization of AA A, splits the product between A and A.t. m Optimal structure m Overlapping sub-problems6 清华大学 宋斌恒 31 Find the least operation to get the result n Direct divide and conquer method, one get the recurrence formula n Catalan number grows as ? (4n /n3/2) å - = = - 1 1 ( ) ( ) ( ) n k P n P k P n k 清华大学 宋斌恒 32 The structure of an optimal parenthesization n If a parenthesis is an optimal one then its sub parenthesis is optimal for the sub-problems 清华大学 宋斌恒 33 A recursive solution { } ïî ï í ì + + + < = = - £ £ mi k m k j p p p i j i j mi j i k j i k j min [ , ] [ 1, ] if 0 if [ , ] 1 清华大学 宋斌恒 34 Computing the optimal costs 15125 11875 10500 9375 7125 7875 4375 2500 3500 5375 15750 2625 750 1000 0 0 0 0 0 0 5000 m[i,j] i=1 i=6 i=2 j=1 j=6 A1 A2 A3 A4 A5 A6 Matrix dimension 30,35,15,5,10,20,25 清华大学 宋斌恒 35 Constructing an optimal solution n S[i,j] records the values of k such that the optimal parenthesization of AiAi+1… Aj splits the product between Ak and Ak+1. 清华大学 宋斌恒 36 Elements of dynamic programming n Two important points n Optimal structure n Overlapping sub-problems