白东程子太军 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) =