费用递归函数 The optimal structure of the binary search tree e[jl, the optimal If the tree is optimal then its all subtree is xpectation value for the ■ Prove it! the key k to k, we have ■ej|=p+(e1]+w(F 1)+er+1+wr+1J) ■e}=e[r1}+er+1』w( Chapter notes aR. Bellman' s systematic study on dynamic programming in 1955 with solid math base solution by Hu and Shing a Knuth posed a question is there any solution the answer is yes with a solution with o(mn/lg n)by Masket and Paterson 清华太学未证想7 清华大学 宋斌恒 37 费用递归函数 n e[i,j ], the optimal expectation value for the optimal tree n If kr is the root of the optimal subtree containing the key ki to kj , we have n e[i,j ]=pr+(e[i,r-1]+w(i,r- 1))+e[r+1,j]+w(r+1,j)) n e[i,j ]=e[i,r-1]+e[r+1,j]+w(i,j) k1 k3 k4 k2 d0 d1 d2 d3 d4 清华大学 宋斌恒 38 The optimal structure of the binary search tree n If the tree is optimal, then its all subtree is optimal. n Prove it! 清华大学 宋斌恒 39 Chapter notes n R. Bellman’s systematic study on dynamic programming in 1955 with solid math base n Matrix chain production has an O(n lg n) solution by Hu and Shing n Knuth posed a question is there any solution whose complexity is less than O(mn) for LCS, the answer is yes with a solution with O(mn/lg n) by Masket and Paterson