动态规划 东南大学计算机学院方效林
东南大学计算机学院 方效林 动态规划
本章内容 动态规划原理 ■矩阵连乘 钢条切割 最长公共子序列 最优二叉搜索树 流水作业调度 0背包问题
本章内容 ◼ 动态规划原理 ◼ 矩阵连乘 ◼ 钢条切割 ◼ 最长公共子序列 ◼ 最优二叉搜索树 ◼ 流水作业调度 ◼ 0/1背包问题 2
动恋规划原理 n与分治法类似,动态规划法也是把问题一层 层地分解为规模逐渐减小的同类型的子问题 分治法 子问题是相互独立的 口若不独立,将重复计算 动态规划 口可分为多个相关子问题 口子问题的解被重复使用 口子问题只求解一次,结果保存在表中,以后用到时 直接存取
动态规划原理 ◼ 与分治法类似，动态规划法也是把问题一层一 层地分解为规模逐渐减小的同类型的子问题 ◼ 分治法 子问题是相互独立的 若不独立，将重复计算 ◼ 动态规划 可分为多个相关子问题 子问题的解被重复使用 子问题只求解一次，结果保存在表中，以后用到时 直接存取 3
动恋规划原理 动态规划的条件 口最优子结构 当一个问题的最优解包含了子问题的最优解时,称这 个问题具有最优子结构 口重叠子问题 在问题的求解过程中,很多子问题的解将被多次使用
动态规划原理 ◼ 动态规划的条件 最优子结构 ➢ 当一个问题的最优解包含了子问题的最优解时，称这 个问题具有最优子结构 重叠子问题 ➢ 在问题的求解过程中，很多子问题的解将被多次使用 4
矩阵连乘 a两矩阵A和B,其维数分别是pxq和qxr,这两 矩阵相乘需进行 pxxN次乘法
矩阵连乘 ◼ 两矩阵A和B，其维数分别是pq和qr，这两 矩阵相乘需进行pqr次乘法 5