动态规划题目分析

1、动态规划题目分析题目目录n走迷宫问题（maze）n叠放箱子（boxes）n走道铺砖（floor）n三色二叉树（tro）n艺术馆火灾（fire）n打砖块（birke）n火车调度（rail）n重建道路（roads）走迷宫问题（maze）n给你N*N的格子，每个格子里面有一个数。n从左上角出发，每次可以向上下左右四个方向最多移动K格。n并且规定每次到达的格子的数字必须大于上一次所在方格的数字。n要求你走过的方格的所有数之和最大，并输出这个最大和。题目分析n我们可以把这个矩阵变为一个图，每个格子看成一个点，如果某个格子能够到另外一个格子，则连一条有向边。n我们可以看到这是一个有向图，那么对于某个点有影

2、响的点是数字比它小的点。题目分析n那么我们可以得到方程：nFi,j=max(fx,y)+ai,j(点(x，y)能够到达点(i，j)n那么方程怎么实现转移呢？n我们可以分析，如果当某个点被扩展时，那么这个点要达到最优状态，及这个点不能被其它没扩展的点到达。n怎样处理呢？我们知道当某个点的数比这个数小时，就有可能到达这个点，我们就可以先把这些点从小到大排序，然后一次处理即可。n处理时是像广搜一样由已知状态扩展到未知状态，n时间复杂度：O（NNK）；叠放箱子（boxes）n有一批箱子，编号为1到N。n每一个箱子都有自身重量和可承受重量。n现在要把这些箱子叠放在一起，并且要满足这些条件：n一、每个箱子

3、上最多只能直接叠放直接叠放一个箱子；n二、编号较小的箱子不能放在编号较大的箱子之上；n三、每个箱子之上的所有箱子重量之和不得超过该箱的可承受重量。n问最多可以叠放多少箱子。题目分析n对于这题目输出方案，我们可以用记录某个状态是由那个状态得到的，这样我们可以得到方案数。n那么怎样求最大的叠放数呢？我们不妨倒过来分析：Fi,j表示后面编号为I到N的物品到达重量为J时最多可以放多少个物品，方程为：nFI,j=max(fi+1,j-mi+1(满足j-mi=wi),fi+1,j),我们再用LaI,j记录这个状态是由fi+1,laI,j得到的。n时间复杂度为：O（3000N）走道铺砖（floor）n给你N

4、*M的图（N*M为偶数），然后用1*2的方块把这个图全部铺满。n问有多少个不同本质的方案。nMin(n,m)=12;n,mm)时，那么对于状态X搜索时只能竖放砖头。n答案就是Fn,2m-1。n时间复杂度：O（m22n）。n注意要用高精度。三色二叉树（tro）n给你一颗二叉树，某个节点有可能只有一个儿子节点。n然后给这些节点染成3种颜色，0，1，2n要求：一个节点与其子节点的颜色必须不同 ；如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同 。n问最多和最少有多少个点能被染成0。题目分析n我们知道这个问题是要在树上进行动态规划，那怎样划分状态呢？n能够影响一个节点的状态只有它的儿子节点，

5、设Froot,j表示以根节点为root的子树时，且节点root染成j这颜色所需求最少的0颜色是多少。n方程为FI,j=max(fi.l,p1+fi.r,p2+da)且(p1p2j；当j=0时da=1否则da=0,).n同理我们也可以求出最少需要多少0；n时间复杂度：O(N);艺术馆火灾（fire）n由LSY讲解打砖块（brike）n在一个凹槽中放置了n层砖块，最上面的一层有n块砖，第二层有n-1块，最下面一层仅有一块砖。第i层的砖块从左至右编号为1，2，i，第i层的第j块砖有一个价值ai,j（ai,j1，则你必须先敲掉第i-1层的第j和第j+1块砖。n你的任务是从一个有n（n=50）层的砖块堆

6、中，敲掉(m=500)块砖，使得被敲掉的这些砖块的价值总和最大。题目分析n我们先把这些砖块都向左移动，使他成直角三角形。n如果把位置（i，j）的砖块打掉，那么就必须把位置（i-1，j）和（i-1，j+1）的砖块打掉。n那么对于位置（x，y），yj的是不会影响位置（i，j）的。题目分析n我们把状态重新定义：n如上图，FI,J,K表示新位置（I，J）时打掉了K快砖之后所得到的最大价值总和。nFI,j,k=max(fi-1,p,k-j+daI,j)n用滚动数组来求解即可。n时间复杂度为：O（N3K）,通过优化可以降为O（N2K）铁路调度（rail）n给你N(N=250)列火车的进站和出站时间。n然后

7、给你M（M=3）个轨道。n问你最多能够进站多少量火车。题目分析n由于M不同，所用的方法也不同。n但我们可以把列车先按出站时间排序。nM=1：fi表示前I辆列车进站且第I辆列车刚刚进站最多有多少量列车。nM=2：FI,k1,k2，表示处理前I辆列车且，进站的列车为K1，K2时最多能进多少辆。题目分析nM=3：可以用状态（a，b，c）来表示，且出站时间a=b=c。n如果对于状态（b，c，d），且d的入站时间大于a的出站时间的话，就状态（a,b,c）向状态（b,c,d）连一条有向边，权值为1。n建立一个起点，对入度为0的状态加入一条边权为3的有向边。n在建立一个终点，使出度为0的状态连向它，且权值为0。n那么最优值是从起点到终点的最长路（这个图无环）。重建道路(roads)n给你N个节点的树。n问你最少毁坏多少条边使得有一个节点为P的子树。题目分析n由于我开始看错了题，所以想了另一个方法。n我们可以看出这是树形DP。n首先可以把这颗森林变为二叉树（及左儿子，右兄弟），且节点1为这可树的根设Di表示在原树中这个子树的节点个数。nFI,j表示在新树中以