简单动态规划入门.ppt

动态规划 使用动态规划的条件 1、最优子结构 2、无后效性 最优子结构 最短路径：如果某条路径是起点到终点的最短路径，则起点到该路径上的每一点都是最短路径。（最长路径？） 无后效性 最短路径：当前选择任何一条边都不会影响以后选择其他边。 有费用的最短路径：设经过任何一条边时都要耗费一定的费用，总费用一定的情况下，当前选择某一条特定的边可能导致某些其他的边无法被选择。 动态规划解题的步骤 1、找出最优子结构 2、写出动态规划方程 3、使用自底向上或者自顶向下的方法求解 4、逆推求解 动态规划的重点 思路与方程 程序模型 线型动态规划 特征：问题的数学模型表现为线型。 通常的子结构划分方式：顺序、中分 最长递减子序列 给定数列a1、a2、…、an，求最长递减子序列。 子结构划分：顺序。 最优子结构？ 无后效性？ 动态规划方程 变量的定义： ai ::= 数列的第i个数 fi ::= 以ai结尾的最长递减子序列长度 方程： fi = max{fk} + 1 0 = k i，ak ai or k = 0 f0 = 0 Answer = max{fi} 1 = i = n 要点小结 动态规划方程要点：变量定义，方程递归形式，参数范围，初始条件。 程序模型要点： 初始条件-变量初始化|递归终止条件 参数范围-循环变量范围判断条件 方程递归形式-赋值语句 矩阵乘法 一个a*b的矩阵和一个b*c的矩阵相乘需要a*b*c次乘法，得到一个a*c的矩阵。现在给你一系列矩阵的连乘式，求最少的乘法次数。 子结构划分：中分。考虑最后两个矩阵相乘。这两个矩阵必定对应某一个划分，由左右两部分分别计算得到。 最优子结构？ 无后效性？ 动态规划方程 变量的定义： ri ::= 第i个矩阵的行数 ci ::= 第i个矩阵的列数 fi j ::= 将第i-j个矩阵相乘所需的最少乘法次数 方程： fi j = min{fi k + fk+1 j} + ri*ck*cj i = k = j fii = 0 Answer = f1 n 取数游戏 有n个数a1、a2、…、an。每次从中删去一个数，规定最左最右两个数不能删除。这样共进行n-2次，求得分最高的方案。 计分方式：设某一次删除的数为ai，则你的得分为ai-1*ai*ai+1。所有得分相加即为最后总分。 动态规划方程 变量的定义： fi j ::= 第i-j个数所能得到的最高得分 方程： fi j = max{fi k + fk j} + ai*ak*aj 1=ikj=N fi i+1 = 0 Answer = f1 n 最长公共子序列 给定两个字符串S和T，求其最长公共子序列。 动态规划方程 变量的定义： fi j ::= S1 i和T1 j的最长公共子序列长度 方程： fi j = max{fi-1 j, fi j-1 , fi-1 j-1+Si=Tj} 1=i=Length(S) 1=j=Length(T) f0 j = fi 0 = 0 Answer = fLength(S) Length(T) 01背包 若01背包问题中，背包容量上限为T(=100)。求解。 动态规划方程 变量的定义： Vi ::= 第i件物品的体积 Pi ::= 第i件物品的价值 fi j ::= 用容量为j的背包去装前i个物品所能 获得的最大总价值 方程： fi j = max{fi-1 j, fi-1 j-vi+Pi} f0 j = 0 Answer = fn T 环型动态规划 特征：问题的数学模型表现为环型。 通常思路：转换成线型处理 石子合并 在一个圆形操场的四周摆放着N堆石子(N= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数。记为该次合并的得分。求最小得分。 动态规划方程 变量的定义： Si j ::= 第i-j堆石子总数 fi j ::= 第i-j堆石子所能得到的最小得分 方程： fi j = min{fi k + fk+1 j} + Si j 1=i=k=j=N fi i = 0 Answer = f1 n 平面型动态规划 特征：问题模型为一个平面 通常的子结构划分方式：逐行扫描 迷宫宝藏 一个迷宫，入口位于左上角，规定只能往下或者往右走。迷宫中存在一些障碍物无法通过。迷宫的某些地方里藏有不同价值的宝藏。求所能收集的宝藏的最大价值。 子结构划分：逐行扫描。考虑迷宫某一点，要求走到这一点所能收集的宝藏的最大价值，先求出走到它左边和上边所能收集的宝藏的最大价值。 最优子结构？ 无后效性？ 动态规划方程 变量的定义： Ai j ::= 迷宫第i行第j列的宝藏价值，-1表示障碍物