归东程子太军 1.4设计步骤 SHANDONG UNIVERSITY OF TECINOLOGY 3会清3合3会3会餐A是会品 1.分析最优解的结构； 2.递归地定义最优值； 3.自底向上地计算出最优值，并获取构造最优解 的信息； 4.根据构造最优解的信息构造优化解。 2025年4月3日 11
2025年4月3日 11 1.4 设计步骤 1.分析最优解的结构； 2.递归地定义最优值； 3.自底向上地计算出最优值，并获取构造最优解 的信息； 4.根据构造最优解的信息构造优化解
归东理子太军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 会会是会会8会 一、 动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树 2025年4月3日 12
2025年4月3日 12 提纲 一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树
归本程子末军 2.1问题定义 HANDONG UNIVERSITY OF TECINOLOGY 华器会合冷的品 O Matrix-chain Multiplication ●输入：<A1,A2,An>,A是矩阵，A与A+1可乘， i=1,2,.(n-1)i ●输出：计算A1×A2×.×A的最小代价方法 矩阵乘法的代价/复亲性：乘法的次数 若A是DX矩阵，B是I灯矩阵，则AXB 的代价是Op4r) 2025年4月3日 13
2025年4月3日 13 2.1 问题定义 ⚫Matrix-chain Multiplication ⚫ 输入：<A1 ,A2 ,.,An>,Ai是矩阵，Ai与Ai＋1可乘， i＝1,2,.(n-1)； ⚫ 输出：计算A1A2.An的最小代价方法 矩阵乘法的代价/复杂性: 乘法的次数 若A是pq矩阵，B是qr矩阵，则AB 的代价是O(pqr)
归东理子太军 2.1问题定义 SHANDONG UNIVERSITY OF TECINOLOGY 华器会空空合安的会器空会的会 ●矩阵连乘法的实现 ■矩阵乘法满足结合律； ■计算一个矩阵链的乘法可有多种方法： 例如，（A×A2×A3×A4） =（A1×(A2×(A3×A4) =（(A×A2)x(A3xA4)) =(（A1×A2)×A3)xA4) 2025年4月3日 14
2025年4月3日 14 2.1 问题定义 ⚫矩阵连乘法的实现 ◼矩阵乘法满足结合律； ◼计算一个矩阵链的乘法可有多种方法: 例如, （A1A2A3A4） =（A1(A2(A3A4 ))) =（(A1A2 )(A3A4）) . = (（A1A2）A3 )A4 )
归东程子太军 2.1问题定义 HANDONG UNIVERSITY OF TECINOLOGY 3会清3会合3会学3华A器会察 ●完全加括号的矩阵连乘积可递归地定义为： (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可 表示为2个完全加括号的矩阵连乘积B和C的 乘积并加括号，即A=(B*C) 给定n个矩阵{A1,A2.,An},其中A与A#1是可乘 的，设矩阵A的维数为P1×p1,=1,2.,n-1。如 何确定计算矩阵连乘积的计算次序（即如何完全加 括号)，使得依此次序计算矩阵连乘积需要的乘法 次数最少。 2025年4月3日 15
2025年4月3日 15 2.1 问题定义 ⚫ 完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可 表示为2个完全加括号的矩阵连乘积B和 C 的 乘积并加括号，即A=(B*C) 给定n个矩阵｛A1 ,A2 ,.,An｝，其中Ai与Ai+1是可乘 的，设矩阵Ai的维数为pi-1 pi，i=1，2.，n-1。如 何确定计算矩阵连乘积的计算次序（即如何完全加 括号），使得依此次序计算矩阵连乘积需要的乘法 次数最少