动态规划forXP

1、动态规划动态规划郭郭 阳阳 东北大学数学系东北大学数学系 2015 2015年年6 6月月学习目标理解状态和状态转移方程理解最优子结构和重叠子问题熟练有向无环图（DAG）上动态规划的常见思路、两种状态定义方法和刷表法掌握记忆化搜索在实现方面的注意事项掌握记忆化搜索和递推中输出方案的方法动态规划的重要性动态规划是算法竞赛的宠儿 几乎所有算法竞赛或招聘中都有这种题目数字三角形问题问题描述a. 第i层有i个结点；b. 每个结点赋予一个非负整数；c. 从顶层按箭头走到底层，如何走使途中数和尽量大？问题分析 若有n层，则完整路线共有 ? 条； 12n当n很大时遍历法的速度将让人无法忍受数字三角形问题状态

2、a. 给结点编号b. 把位置(i,j)看成一个状态；c. 定义状态(i,j)的指标函数d(i,j)为从结点(i,j)出发时能得到的最大和（包括结点(i,j) 本身的值）注意：在这个状态定义下，原问题的解是d(1,1)。数字三角形问题状态转移方程 d(i,j)=a(i,j)+maxd(i+1,j), d(i+1,j+1) 其中a(i,j)是结点中的值。 原理：如果连“从(i+1,j)出发走到底部”这部分的和都不是最大，加上a(i,j)之后肯定也不是最大的。这个性质称为最优子结构，也描述为“全局最优解包含局部最优解”数字三角形问题递归算法递归算法：int solve(int i, int j) r

3、eturn aij + (i=n?0:max(solve(i+1,j), solve(i+1,j+1);(1) 输入solve(1,1)即可递归出结果；(2) 正确但效率低，大量重复计算；(3) 调用关系树共有 ？ 个结点 21n11 (1 2 )1+2+4+2211 2nnn程序Prog1数字三角形问题递推算法递推算法：int i, j; for(j=1; j=1; i-) for(j=1; j=0 ) return dij; return dij =aij + (i = n ? 0 : max(solve(i+1, j), solve(i+1, j+1); (2) 虽递归，但判断dij=0

4、保证每个结点只访问一次(3) 时间复杂度： O( )2n程序Prog3数字三角形问题 - 总结遍历法：完整路线有 条，让人无法忍受；递归法：共 个结点需要计算指标，重复计算；递推法：共有 个结点需要计算指标，无重复计算，需要事先确定计算顺序（逆序枚举）；记忆化搜索法：共有 个结点需要计算指标，无重复计算，不必事先确定各状态的计算顺序，但需要记录每个状态“是否已经计算过”。12n21n(1)/ 2n n(1)/ 2n n22nn计算量从是一个巨大的优化！？作业一：数字三角形 找出数字之和最大和最小的路径分别打印出来找出数字之和最大和最小的路径分别打印出来有向无环图（DAG）上的动态规划DAG：D

5、irected Acyclic Graph非有向无环图：很多问题很多问题 DAG上的最长路、最短路或路径计数问题上的最长路、最短路或路径计数问题矩形编号DAG模型之一：嵌套矩形问题问题描述问题描述：有n个矩形，每个矩形可用两整数a, b描述(长和宽)。矩形X(a,b)可以嵌套在矩形Y(c,d)中，当且仅当ac, bd, 或者ad, bc。 例如: (1, 5) is in (6, 2), but not in (3, 4).任务任务：选出尽量多的矩形排成一行，下一个嵌套前一个。如果有多解，矩形编号的字典序尽量小。分析分析： (1) “可嵌套”是二元关系，可用图来建模； (2) 该图定是DAG，

6、因为自己不能嵌套自己； (3) 本质上求DAG上的最长路径。ABCD 0) return ans; ans = 1; for (int j = 1; j=n; j+) if (Gij) ans = max(ans, dp(j) +1); return ans;引用等于给变量起了另一个名字，用引用名=使用该变量，引用实际是地址传递，因为引用名和变量用的是同一个内存。用用i=1,，6来表示来表示A,F最终有最终有3条长度为条长度为3的最长嵌套序列，如何确定字典序最小的结果呢？的最长嵌套序列，如何确定字典序最小的结果呢？嵌套矩形问题 - 字典序最小有多个最优解，如何选择矩形编号的字典序最小？(1)

7、将所有指标d值计算出来后，选择最大di所对应的i。若有多个i, 则选择最小的i, 以保证字典序最小。如：如：d(A)=d(H)=3; 则选矩形则选矩形A作为最长嵌套序列的起点。作为最长嵌套序列的起点。(2) 然后选择满足d(i)=d(j)+1中字典序最小的j。void print_ans(int i) printf (“%d”, i); for (int j=1; j=n; j+) if (Gij) & (di=dj+1) print_ans(j); break; 它们保证了输出的是从第它们保证了输出的是从第i个矩形出发按字典序最小的嵌套结果个矩形出发按字典序最小的嵌套结果程序Prog

8、A1作业二：嵌套矩形问题已知矩形分别为： A(1,2), B(5,8), C(5,9), D(6,9), E(6,8), F(7,9), G(7,10), H(6,10), I(5,10), J(8,11)问题：找出字典序最小的最长矩形嵌套序列嵌套矩形问题 - 字典序最小问题一：若想打印出所有方案，如何编写程序？ 问题二：若把状态定义为“d(i)表示以结点i为终点的最长路径长度”，如何求最优值？问题二中很难打印字典序最小的方案，why？因为此时是从右向左确定矩形，从右向左字母都因为此时是从右向左确定矩形，从右向左字母都取最小并不能保证整体字典序最小。例如：取最小并不能保证整体字典序最小。例如：

9、ABCF ABDE硬币问题问题描述问题描述： 有n种不同面值的硬币(每种无限多)。 任务任务： 给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。12,nV VV硬币问题固定终点的最长路和最短路 (求法类似)定义状态：d(i)为从结点i出发到结点0最长路径长度(1) 与嵌套矩形问题相似(2) 不同之处：a. 硬币问题中路径长度可以为0（当S=0时），所以不能用d(i)=0来表示“还没有算过”，即不能把d全设为0来初始化，而应该赋予一个一般情况下都取不到的值，如-1，memset(d, -1, sizeof(d)b. 结点S不一定真的能到达结点0，需用特殊的

10、dS值表达“无法到达”d数组的长度等于整数数组的长度等于整数S硬币问题 - 特殊值表示“没算过”（记忆化搜索）程序：int dp(int S) int & ans = dS;if(ans != -1) return ans;ans = -(130);for (int i = 1; i=Vi) ans = max(ans, dp(S-Vi)+1);return ans;固定起点固定起点按位左移，等于按位左移，等于-230. 表表示示S不能正常分解为不能正常分解为0又是引用又是引用硬币类数硬币类数嵌套问题是满足嵌套问题是满足G(i,j)=1可嵌套性，可嵌套性，这里采用的是只要这里采用的是只

11、要大于币值，就相当大于币值，就相当于可嵌套了于可嵌套了程序ProgA2建长度为S的数组vis, 使visi表示状态i是否被访问过初始化 memset(vis, 0, sizeof(vis)int dp(int S) if (visS) return dS;visS = 1;int & ans = dS;ans = -(130);for (int i = 1; i=Vi) ans = max(ans, dp(S-Vi)+1);return ans;硬币问题 - 新建数组标签（记忆化搜索）以占用一些内存为代价增强程序的可读性，减少出错的可能程序ProgA3硬币问题 - 递推法同时求最大和最

12、小minv0 = maxv0=0;for(int i=1; i=S; i+) minvi = INF; maxvi = -INF; for(int i = 1; i=S; i+) for (int j =1; j= Vj ) minvi = min(minvi, minvi-Vj+1); maxvi = max(maxvi, maxvi-Vj+1); printf(“%d %dn”, minvS, maxvS);minv和和maxv中第中第i个分量存的是从钱数个分量存的是从钱数i到到0的的最小和最大分解长度最小和最大分解长度从小到大额求最小和最大分解长度从小到大额求最小和最大分解长度 设设V1

13、=3; V2=6; 当当i=3时时, minv3 = min(minv3, minvi-V1+1)=min(INF, minv0+1)=1;同理，同理，maxv3=1; 当当i=5时？时？当当i=6, j=1时，时，minv6=min(minv6, minv6-V1+1)=min(INF, minv3+1)= 2; maxv6=max(maxv6,maxv6-V1+1)=max(-INF,maxv3+1)=2;当当i=6, j=2时，时， minv6=min(minv6, minv6-V2+1)= min(2, 1)=1; maxv6=max(maxv6,maxv6-V2+1)=max(2,m

14、axv0+1)=2;程序ProgA4硬币问题 输出字典序最小的方案void print_ans(int* d, int S) for(int i =1; i=Vi & dS = dS-Vi+1) printf(%d, i); numi +; print_ans(d, S-Vi); break; 执行print_ans(minv, S)和print_ans(maxv, S)即可此时此时d=minv此时此时d=maxv从小到大的循环保证从小到大的循环保证了字典序最小方案了字典序最小方案分解中第分解中第 i 类硬币的个数类硬币的个数硬币问题 递推同时记录路径，最后打印递推时直接用数组min_

15、coinS记录满足minvS=minvS-Vj+1的最小的j。for(int i = 1; i=S; i+) for (int j =1; j= Vj ) if (minvi (minvi-Vj +1) minvi = minvi-Vj+1; min_coini = j; if (maxvi (maxvi-Vj+1) maxvi = maxvi-Vj+1; max_coini = j; 求出min_coin和max_coin后，调用print_ans(min_coin, S)和print_ans(max_coin, S)即可得各自字典序最小路径。void print_ans(int* d, int S) while(S) printf(%d, dS); numdS +; S -= VdS; 典型的“用空间换时间”：用数组避免