第3章：动态规划 Dynamic Programming
第3章：动态规划 Dynamic Programming
知识要点 3理解动态规划算法的概念 ?掌握动态规划算法的基本要素 Φ最优子结构性质 Φ重叠子问题性质 ?掌握动态规划算法的设计方法 Φ找出最优解的性质，并刻划其结构特征 Φ递归地定义最优值 Φ以自底向上的方式计算出最优值 Φ根据计算最优值时得到的信息，构造最优解
知识要点 理解动态规划算法的概念 掌握动态规划算法的基本要素 最优子结构性质 重叠子问题性质 掌握动态规划算法的设计方法 找出最优解的性质，并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息，构造最优解
知识要点 ?通过应用范例学习动态规划算法设计策略 Φ矩阵连乘问题 Φ最长公共子序列问题 Φ最大子段和问题 Φ凸多边形最优三角剖分问题 Φ图像压缩问题 Φ0-1背包问题
知识要点 通过应用范例学习动态规划算法设计策略 矩阵连乘问题 最长公共子序列问题 最大子段和问题 凸多边形最优三角剖分问题 图像压缩问题 0-1背包问题
算法总体思想 ■ 动态规划算法与分治法类似，其基本思想也是将待求 解问题分解成若干个子问题 T(n/2) T(n/2) T(n/2) T(n/2) 4
4 ◼ 动态规划算法与分治法类似，其基本思想也是将待求 解问题分解成若干个子问题 算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2)
算法总体思想 但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时，有些子问题被重复计算了许多次。 n/2 n12 n/2 n/2 T64T64T64T614)T4T4T14T04)T14T4T4T4)T14T14T4T4) 5
5 ◼ 但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时，有些子问题被重复计算了许多次。 算法总体思想 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)