动态规划基础和建模

1、动态规划基础和建模第1页，共105页，2022年，5月20日，20点45分，星期一动态规划是统筹学的重要内容动态规划是OI的重要内容据不完全统计，每次考试动态规划起码有一道题前言动态规划很重要 ！第2页，共105页，2022年，5月20日，20点45分，星期一这个课件的目的：对动态规划的模型进行了一些总结有部分内容超出了NOIP范围为同学们提供一个刷题的方向请同学们踊跃发言前言第3页，共105页，2022年，5月20日，20点45分，星期一阶段状态决策状态转移状态转移方程动态规划的基本概念第4页，共105页，2022年，5月20日，20点45分，星期一最优子结构无后效性原则重叠子问题动态规划的

2、基本概念DP是一种记忆化的思想第5页，共105页，2022年，5月20日，20点45分，星期一拓展一下：阶段 - 拓扑序状态 - 点状态转移 - 边决策 - 前驱？DFA？动态规划的基本概念DP是状态空间上的最短（长）路或者可行路第6页，共105页，2022年，5月20日，20点45分，星期一实现方式：递推：顺推和逆推记忆化搜索前者灵活，优化方法多后者可以减少不必要节点的计算动态规划的基本概念第7页，共105页，2022年，5月20日，20点45分，星期一时间复杂度：状态数*转移费用动态规划的基本概念第8页，共105页，2022年，5月20日，20点45分，星期一线性模型区间模型矩形模型树形模

3、型背包模型图状模型SCDP多线程DP多重DP更广泛的动态规划的模型第9页，共105页，2022年，5月20日，20点45分，星期一单线问题：上楼梯问题LIS问题乌龟棋诗人小G（简化版）双线问题：LCS问题模糊匹配线性模型第10页，共105页，2022年，5月20日，20点45分，星期一Zbwmqlw神犇要上楼梯，他一次可以上一层，也可以上两层。楼梯有n层有多少种上楼梯的方案上楼梯问题第11页，共105页，2022年，5月20日，20点45分，星期一N=107？设fi表示到第i层得方案数前一步可以上一层也可以上两层Fi=fi-1+fi-2N=1015？矩阵乘法上楼梯问题第12页，共105页，20

4、22年，5月20日，20点45分，星期一给定一个数列an，求它的一个子序列bm满足b1b2b3bm使得m最大N=10000LIS问题第13页，共105页，2022年，5月20日，20点45分，星期一设fi表示以i结尾的LIS的长度Fi=maxfj+1,ji且ajai时间复杂度？O(n2)如何优化？LIS问题第14页，共105页，2022年，5月20日，20点45分，星期一对于i来说，如果存在一个长度为len的LIS以i结尾，那么也一定存在长度=ai的最大的kFi=k+1时间复杂度O(nlogn)LIS问题第15页，共105页，2022年，5月20日，20点45分，星期一乌龟棋（NOIP2010

5、t）第16页，共105页，2022年，5月20日，20点45分，星期一Fiabcd表示到位置i，四种操作分别进行了a,b,c,d次决策有四种时间复杂度：O(nc4)TLE+MLE乌龟棋第17页，共105页，2022年，5月20日，20点45分，星期一乌龟棋第18页，共105页，2022年，5月20日，20点45分，星期一一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G

6、不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P 次方，而一个排版的不协调度为所有行不协调度的总和。小G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。诗人小G（NOI2009）简化版第19页，共105页，2022年，5月20日，20点45分，星期一Fi表示前i句诗的最小不协调度Fi=minfj+(sumi-sumj+i-j-L)p时间复杂度O(n2)优化？导数证明四边形不等式，有兴趣的同学自己查阅有关资料诗人小G第20页，共

7、105页，2022年，5月20日，20点45分，星期一给定两个字符串s，t求最长公共字串例：abcde和ace的LCS是aceN=1000LCS问题第21页，共105页，2022年，5月20日，20点45分，星期一设fij表示第一个串到i，第二个串到j的LCSFij=fi-1j-1+1, si=tj =minfi-1j,fij-1, si!=tj时间复杂度O(n2)LCS问题第22页，共105页，2022年，5月20日，20点45分，星期一给定两个字符串s和t，每个字符串有英文字母和*？！组成，*？！的含义分别是：*：匹配一个或多个字符；？：匹配至少一个至多三个字符；！：匹配至少三个字符。问两

8、个字符串是否能够匹配。N=1000模糊匹配（POJ1229）第23页，共105页，2022年，5月20日，20点45分，星期一模糊匹配第24页，共105页，2022年，5月20日，20点45分，星期一石子归并回文词决斗问题Blocks区间模型第25页，共105页，2022年，5月20日，20点45分，星期一有n堆石子，第i堆重ai每次可以合并相邻两堆合并费用为新堆的重量 求合并成一堆的最小费用N=200石子归并第26页，共105页，2022年，5月20日，20点45分，星期一合并的费用是一段的和设fij表示合并i到j的一段Fij=minfik+fk+1j+sumij时间复杂度O(n3)石子归并

9、第27页，共105页，2022年，5月20日，20点45分，星期一给定一个字符串s，要求添加最少的字符，使得s成为一个回文串。N=5000回文词（IOI2000）第28页，共105页，2022年，5月20日，20点45分，星期一abcba：回文abcbc：不回文Fij表示i到j变成回文的最小代价Fij=fi+1j-1, si=sj =minfi+1j,fij-1+1, si!=sj时间复杂度O(n2)回文词第29页，共105页，2022年，5月20日，20点45分，星期一N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（即第i个人与第i+1个人决斗，第N个人与第1个人决斗），死者退出，最

10、终剩下的人胜利。将任意两个人之间决斗的输赢情况告诉你，决斗顺序由你安排，问哪些人可能成为最终的胜利者？Nfi+1 =maxgp,hp+1,fp=fi+1树的最长链第62页，共105页，2022年，5月20日，20点45分，星期一给定一棵树，求树的最小点支配集。N=10000支配集：点覆盖点Cell Phone Network（POJ3659）第63页，共105页，2022年，5月20日，20点45分，星期一Cell Phone Network第64页，共105页，2022年，5月20日，20点45分，星期一Cell Phone Network第65页，共105页，2022年，5月20日，20点

11、45分，星期一Cell Phone Network第66页，共105页，2022年，5月20日，20点45分，星期一 设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分 subtree的右子树的加分subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,n）且加分最高的

12、二叉树tree。要求输出； （1）tree的最高加分 （2）tree的前序遍历加分二叉树（NOIP2003）第67页，共105页，2022年，5月20日，20点45分，星期一加分二叉树第68页，共105页，2022年，5月20日，20点45分，星期一部分背包01背包完全背包多重背包分组背包依赖背包泛化物品背包模型第69页，共105页，2022年，5月20日，20点45分，星期一给定一个容量为m的背包和n个物品，每个物品有一个价值v和一个费用w，求在满足容量限制的情况下最大化价值。NPC问题背包问题第70页，共105页，2022年，5月20日，20点45分，星期一特点：物品可以任意划分方法：求单

13、位价值，贪心部分背包问题第71页，共105页，2022年，5月20日，20点45分，星期一01背包问题第72页，共105页，2022年，5月20日，20点45分，星期一空间优化：滚动数组代码：void ZeroOnePack for(int i=1;i=costi;j-) gmax(fj,fj-costi+valuei);01背包问题第73页，共105页，2022年，5月20日，20点45分，星期一完全背包问题第74页，共105页，2022年，5月20日，20点45分，星期一特点：每类问题有个数限制ci基本想法：每类物品的每一个看作一个物品，转化成01背包代码：void LimitedPack

14、 for(int i=1;i=n;i+) for(int j=1;j=costi;k-) gmax(fk,fk-costi+valuei);多重背包问题第75页，共105页，2022年，5月20日，20点45分，星期一优化：二进制拆分原理：2k能够表示出02(k+1)-1的所有数把ci拆成若干2k相加O(nmlogc)多重背包问题第76页，共105页，2022年，5月20日，20点45分，星期一特点：物品被分为很多组，每组之间有限制。假设限制为：每组只能取一个Fij=maxfi-1j,fi-1j-wik+vik代码：void GroupPack for(int i=1;i=mincosti;j

15、-) for(int k=1;k=cnti;k+) if(costik=j) gmax(fj,fj-costik+valueik;分组背包问题第77页，共105页，2022年，5月20日，20点45分，星期一考试的时候合理分配时间是很重要的，我们应该在同样的时间内尽量得到更多的分数。现在有m道题需要在n分钟内解决，每道题分为p个步骤，每道题的每个步骤都会有不同的分值，所需时间也不尽相同。现在你可以从任意一道题的任意一个步骤开始，如果当前步骤与上一步骤不连续，则需要q分钟的思考时间（每题第一个步骤之前同样需要思考），请确定自己的策略使得获得的分数最高。分配时间（WFTSC2009T）第78页，共

16、105页，2022年，5月20日，20点45分，星期一每道题实际上是一个组。我们可以发现，每个步骤选或不选对后面的决策是有影响的，所以我们考虑加一维来区分。设fijk表示前i道题的前j个步骤，其中第i道题的第j个步骤被选，在k分钟内解决的最大得分，gijk表示前i道题的前j个步骤，其中第i道题的第j个步骤不被选，在k分钟内解决的最大得分，那么：分配时间第79页，共105页，2022年，5月20日，20点45分，星期一分配时间第80页，共105页，2022年，5月20日，20点45分，星期一 依赖背包问题，顾名思义，就是一些物品可以选要建立在其它一些物品被选的基础之上。这类问题往往是建立在树上的

17、，所以通常也叫树形背包问题。鉴于在树形模型中已经有了比较详细的讨论，这里不再详细展开依赖背包问题第81页，共105页，2022年，5月20日，20点45分，星期一泛化物品第82页，共105页，2022年，5月20日，20点45分，星期一void GeneralMatters for(int i=1;i=0;j-) for(int k=0;kfj拓扑排序的过程中解决关键路径第91页，共105页，2022年，5月20日，20点45分，星期一给定一个图，边有的是单向的，有的是双向的有一个水晶球，每个点有一个价格从s出发到t，沿途在某个点买入水晶球，在另一个点卖出显然你要先买入才能卖出最大化收益最优贸

18、易（NOIP2009T）第92页，共105页，2022年，5月20日，20点45分，星期一方法一：同一个SCC里的点都可以走到，可以在其中任意一个买，任意一个卖收缩SCC，记录SCC的最大值和最小值Fi表示到i的最大获利，gi表示到i的最小价格，minvi表示i所在SCC的最小价格，maxvi表示i所在SCC的最大价格Gi=mingj,minviFi=maxfj,maxvi-gi边拓扑排序边做最优贸易第93页，共105页，2022年，5月20日，20点45分，星期一方法二：Fi0表示到i点，没有水晶球的最大Fi1表示到i点，有水晶球的最大Fi0=maxfj0,fj1+wifi1=maxfj1,

19、-wi前面说过：动态规划是状态图的最短路或最长路嵌套在SPFA算法中，迭代求解最优贸易第94页，共105页，2022年，5月20日，20点45分，星期一这类问题在NOIP中一般不会出现，但鉴于在NOIP的模拟题和WFTSC中出现了不止一次，稍微提一下插头DP棋盘DP集合DP状态压缩模型第95页，共105页，2022年，5月20日，20点45分，星期一把问题的状态压缩成一个k进制数来表示，利用这个数的每一位反映出来的信息来进行转移问题规模往往特别小状态压缩模型第96页，共105页，2022年，5月20日，20点45分，星期一困惑的旅行家（WFTSC2010T）第97页，共105页，2022年，5

20、月20日，20点45分，星期一经典的TSP问题最优哈密顿回路设fiS表示当前在i点，经过的点的集合是SFiS=minfjS-i+disjiAns=minfi2n-1+disi1困惑的旅行家第98页，共105页，2022年，5月20日，20点45分，星期一多线程动态规划，顾名思义，就是很多条线一起进行的动态规划。这类问题要完整的表达出各条线的特点，转移往往比较简单。多线程动态规划第99页，共105页，2022年，5月20日，20点45分，星期一一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从p到q移动一个员工，需要花费c(p,q)。这个函数没有必要对称，但是c(p,p)=0。公司必须满足所有 的请求。目标是最小化公司花费。Mobile Service（tyvj1061）第100页，共105页，2022年，5月20