分解最优解的结构 将矩阵连乘积AAA记为A[i:j ■若A[1:n]的一个最优解是在矩阵A和A+1处 断开的,即A[1:n]=(A[1:k]A[k+1:n]),则 A[1:k]和Ak+1:n也分别是最优解。 ■事实上,若A[1:k]的一个计算次序所需计算量 更少的话,则用此计算次序替换原来的次序, 则得到A[1:n一个更少的计算量,这是一个矛 盾。同理A[k+1:n]也是最优解 ■最优子结构性质:最优解的子结构也最优的。 算法设计与分析 5算法设计与分析 5 分解最优解的结构 ◼ 将矩阵连乘积AiAi+1…Aj记为A[i: j]。 ◼ 若A[1: n] 的一个最优解是在矩阵Ak和Ak+1处 断开的，即A[1: n] = (A[1: k] A[k+1: n])，则 A[1: k]和A[k+1: n]也分别是最优解。 ◼ 事实上，若A[1: k]的一个计算次序所需计算量 更少的话，则用此计算次序替换原来的次序， 则得到A[1: n]一个更少的计算量，这是一个矛 盾。同理A[k+1: n]也是最优解。 ◼ 最优子结构性质：最优解的子结构也最优的