电子科技大学：《算法设计与分析 Algorithms Design and Analysis》课程教学资源（课件讲稿）第三章 动态规划 Dynamic Programming

第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)

算法总体思想 ■ 如果能够保存已解决的子问题的答案，而在需要时再 找出已求得的答案，就可以避免大量重复计算，从而 得到多项式时间算法。 n12 n/2 n/2 n/2 T4)TA4)T64T(64)TA4)T(64)T(4)TA4T(4)T4) T64) 6

6 ◼ 如果能够保存已解决的子问题的答案，而在需要时再 找出已求得的答案，就可以避免大量重复计算，从而 得到多项式时间算法。 算法总体思想 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)

动态规划算法 CR 算法总体思想 动态规划算法与分治法类似，其基本思想也是将待求解问题 分解成若干个子问题 ⊕ 与分治法的区别在于 适用于动态规划算法求解的问题，经分解得到的子问题往 往不是互相独立的；若用分治法求解，则分解得到的子问 题数目太多，导致最终解决原问题需指数时间， 原因在于：虽然子问题的数目常常只有多项式量级，但在 用分治法求解时，有些子问题被重复计算了许多次 ⊕ 如果可以保存已解决的子问题的答案，就可以避免大量重复 计算，从而得到多项式时间的算法 动态规划法的基本思路是：构造一张表来记录所有已解决的 子问题的答案（无论算法形式如何，其填表格式是相同的）

动态规划算法  算法总体思想  动态规划算法与分治法类似，其基本思想也是将待求解问题 分解成若干个子问题  与分治法的区别在于 ━ 适用于动态规划算法求解的问题，经分解得到的子问题往 往不是互相独立的；若用分治法求解，则分解得到的子问 题数目太多，导致最终解决原问题需指数时间， ━ 原因在于：虽然子问题的数目常常只有多项式量级，但在 用分治法求解时，有些子问题被重复计算了许多次  如果可以保存已解决的子问题的答案，就可以避免大量重复 计算，从而得到多项式时间的算法  动态规划法的基本思路是：构造一张表来记录所有已解决的 子问题的答案（无论算法形式如何，其填表格式是相同的）

动态规划算法的基本步骤 1。找出最优解的性质（分析其结构特征） 2.递归地定义最优值（优化目标函数） 3.以自底向上的方式计算出最优值 4.根据计算最优值时得到的信息，构造最优解

动态规划算法的基本步骤 1. 找出最优解的性质（分析其结构特征） 2. 递归地定义最优值（优化目标函数） 3. 以自底向上的方式计算出最优值 4. 根据计算最优值时得到的信息，构造最优解

3.1矩阵连乘问题 (Matrix-Chain Multiplication)

3.1 矩阵连乘问题 (Matrix-Chain Multiplication)

两个矩阵相乘：标准解法 void matrixMultiply(int **Ma,int **Mb,int **Mc, int ra,int ca,int rb,int cb){ if(caI=rb)error("矩阵不可乘")： for (int i=0;i<ra;i++) for (int j=0;j<cb;j++){ int sum=a[i][o]*b[o][j]; for (int k=1;k<ca;k++) sum +a[i][k]*b[k][j]; } c[i][j]=sum; } } 设A是pXq的矩阵，B是qXr的矩阵，数乘次数为pxqxr 算法的时间复杂度为：O(n3)

两个矩阵相乘：标准解法 • 设A是pⅹq的矩阵，B是qⅹr的矩阵，数乘次数为pⅹqⅹr • 算法的时间复杂度为：O(n3) void matrixMultiply( int **Ma, int **Mb, int **Mc, int ra, int ca, int rb, int cb ) { if (ca != rb) error(“矩阵不可乘”); for (int i=0; i<ra; i++){ for (int j=0; j<cb; j++) { int sum=a[i][0]*b[0][j]; for (int k=1; k<ca; k++){ sum += a[i][k]*b[k][j]; } c[i][j]=sum; } } }