白东程子太军 ANDONG UNIVERSITY OF TBCINOLOO 计算机算法设计与分析 Design and Analysis of ComputerAlgorithms 第三章动态规划 Dynamic Programming 主红霞 理学院
计算机算法设计与分析 Design and Analysis of Computer Algorithms 第三章 动态规划 Dynamic Programming 王红霞 理学院
归东程子末军 学习要点： SHANDONG UNIVERSITY OF TECHNOLOGY 理解动态规划算法的概念。 掌握动态规划算法的基本要素 。（1)最优子结构性质 。（2)重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 2025年4月3日 2
2025年4月3日 2 •理解动态规划算法的概念。 •掌握动态规划算法的基本要素 •（1）最优子结构性质 •（2）重叠子问题性质 •掌握设计动态规划算法的步骤。 •(1)找出最优解的性质，并刻划其结构特征。 •(2)递归地定义最优值。 •(3)以自底向上的方式计算出最优值。 •(4)根据计算最优值时得到的信息，构造最优解。 学习要点:
归本程子末军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树 2025年4月3日 3
2025年4月3日 3 提纲 一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树
归本程子末军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 一、动态规划算法的思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树 2025年4月3日
2025年4月3日 4 提纲 一、动态规划算法的思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树
1.1算法总体思想 山东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 5会清空深会的点会会的是会径 ·动态规划算法与分治法类似，其基本思想也是将待求 解问题分解成若干个子问题 T(n) T(n/2) T(n/2) T(n/2) T(n/2) 2025年4月3日
2025年4月3日 5 ⚫ 动态规划算法与分治法类似，其基本思想也是将待求 解问题分解成若干个子问题 1.1算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) =
1.1算法总体思想 归东程子末军 SHANDONG UNIVERSITY OF TECHNOLOGY 5会器会的六会器会的品会 但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时有些子问题被重复计算了许多次。 T(n) n/2 n/2 n/2 TB 4X4R4T4R4T4R4)TR4T4R4T(B4T(R4)T(RM4X(B4T(R4X(R4)T(R4X(R4X4R4X4B 2025年4月3日 6
2025年4月3日 6 ⚫ 但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时，有些子问题被重复计算了许多次。 1.1算法总体思想 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4)
1.1算法总体思想 归本理子太军 SHANDONG UNIVERSITY OF TECINOLOGY 会空空合会的尽会器会空器会合 如果能够保存已解决的子问题的答案，而在需要时再 找出已求得的答案，就可以避免大量重复计算，从而 得到多项式时间算法。 T(n) n/2 n/2 T(RM4)T(R4) TR4)T(R4)T(R4)T(R4)T(R4)T(R4)T44)T4RM4) T(n4) 2025年4月3日
2025年4月3日 7 ⚫ 如果能够保存已解决的子问题的答案，而在需要时再 找出已求得的答案，就可以避免大量重复计算，从而 得到多项式时间算法。 1.1算法总体思想 = n n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4)T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n)
归东程子末军 1.1总体思想 SHANDONG UNIVERSITY OF TECHNOLOGY 华器会空空合安会器空会的会路 动态规划算透与父迨清似石 某基本思想也是将待求解 问题分解成岩手不学同簸，但芬霹的学尚巅程挂不是 相互独立的。 Divide-.and-conquer技术的问题 ■子问题是相互独立的； 如果子闫题不是担县独立的，分治方法将重复计 算公共学简题，数率很低。 ●1 Dynamic Programming特点 ■把原始问题划分成一系列子问题； ■求解每个子问题区一次，并将基结果保存在个表中， 以后用到时直接荐取，不董复计算，节省计算时间； ■自底向上地计算。 2025年4月3日 d
2025年4月3日 8 1.1 总体思想 ⚫ 动态规划算法与分治法类似，其基本思想也是将待求解 问题分解成若干个子问题，但分解后的子问题往往不是 相互独立的。 ⚫ Divide-and-conquer技术的问题 ◼子问题是相互独立的； ◼如果子问题不是相互独立的，分治方法将重复计 算公共子问题，效率很低。 ⚫ Dynamic Programming特点 ◼ 把原始问题划分成一系列子问题； ◼ 求解每个子问题仅一次，并将其结果保存在一个表中， 以后用到时直接存取，不重复计算，节省计算时间； ◼ 自底向上地计算
归本理子太军 1.2适用范围 SHANDONG UNIVERSITY OF TECINOLOGY 会是33☆ ●适用范围 ■一类最优化问题：可分为多个相关子问题， 子问题的解被重复使用。 ● 最优化问题 ■给定一组约束条件和一个代价函数，在解空 间中搜索具有最小或最大代价的最优解； ■很多最优化问题可分为多个子问题，子问题 相互关联，子问题的解被重复使用。 2025年4月3日
2025年4月3日 9 1.2 适用范围 ⚫适用范围 ◼一类最优化问题：可分为多个相关子问题， 子问题的解被重复使用。 ⚫最优化问题 ◼给定一组约束条件和一个代价函数，在解空 间中搜索具有最小或最大代价的最优解； ◼很多最优化问题可分为多个子问题，子问题 相互关联，子问题的解被重复使用
归东理子太军程 1.3基本要素 SHANDONG UNIVERSITY OF TECHNOLOGY 华器会空空合安会空会的会 ●使用动态规划算法的条件： ■最优子结构(optimal sub-structure) ◆当一个问题的最优解包含了子问题的最优解时，称 这个问题具有最优子结构； ◆最优子结构使得能自底而上地完成求解过程； ◆通常可用“剪贴”(cut and paste))技术判定最优子结 构。 ■重叠子问题(overlapping sub-problems) ◆在问题的求解过程中，很多子问题的解将被多次使 用。 2025年4月3日 10
2025年4月3日 10 1.3 基本要素 ⚫使用动态规划算法的条件： ◼最优子结构(optimal sub-structure) ◆当一个问题的最优解包含了子问题的最优解时，称 这个问题具有最优子结构； ◆最优子结构使得能自底而上地完成求解过程； ◆通常可用“剪贴”(cut and paste)技术判定最优子结 构。 ◼重叠子问题(overlapping sub-problems) ◆在问题的求解过程中，很多子问题的解将被多次使 用