第3章动态规划（第1部分）.pptVIP

第3章 动态规划Part 1 ;学习要点;引言 几个典型问题;问题1：最短路径;问题2：最短路径;问题3：背包问题;问题4：文本相似度问题;3.1 矩阵连乘问题;3.1 矩阵连乘问题;矩阵乘法;矩阵连乘方法数与添括号方式数一一对应;矩阵连乘积与加括号;二、算法分析--穷举法行吗？;二、算法分析--新思路;二、算法分析--新思路;分析最优解的特征和结构;矩阵链问题的一般递推关系;（3）计算最优值;计算最优值程序;算法过程;算法复杂度分析;（4）算法分析--构造最优解;3.2 动态规划算法的基本要素;动态规划的基本思想;求解方法;动态规划中的概念、名词术语(1);动态规划中的概念、名词术语(2);动态规划的求解步骤;动态规划的求解方法;void MatrixChain(int p, int n, int **m, int **s){ for (int i = 1; i = n; i++) m[i][i] = 0; for (int r = 2; r = n; r++ ) for (int i = 1; i = n - r+ l; i++) { int j = i + r - 1; m[i][j] = m[i+1][j] + P[i - 1]*P[i]* P[j]; s[i][j] = i; for (int k = i+1; k j; k++){ int t = m[i][k ] + m[k + 1][j]+ P[i – 1]* p[k] * p[j]; if (t m[i][j]){ m[i][j] = t; s[i][j] = k; } } } ;动态规划算法的基本要素;动态规划算法的基本要素;重叠子结构性质;动态规划法与分治策略;动态规划法与分治策略（续）;备忘录方法;动态规划小结;作业与上机题;动态规划解题举例1;分析;动态规划解题举例2;设F[i][j]为前i个抄写员复制前j本书的最小完成时间数。考察第i人的抄写情况。设前面t本书由前i-1人抄写，而从第t+1，t+2，…，j本书由第i人抄写，于是便有状态转移方程： ;3.3 最长公共子序列;概念;2、公共子序列;最长公共子序问题;一、算法分析;最长公共子序列的结构;结论;二、子问题的递归结构;三、计算最优值;举例;算法的改进;银币问题—补充;补充：银币问题-续 ;3.4 最大子段和;心情愉快指数;最大子段和问题;举例;算法分析;简单算法--枚举;改进算法—递推;分治策略;第三种情况的处理：S=;动态规划方法;动态规划-程序;最大子段和的推广;最大子矩阵和问题;算法;;;最大m子段和问题-自学;作业