HDUWebDIY25道动态规划题的解题报告

个人收集整理-ZQHDUWebDIY25道动态规划题的解题报告 道动态规划题的解题报告（有详细的思路，状态的描述，以及状态转移方程，但不会给出代码，请自己编码）密码：A 最简单的，但很重要。说明了动态规划产生的动机之一：递归产生的大量重复子问题。有两种解决方法，一、记忆化搜索，就是在用递归处理问题的过程中把已经算过的状态记录在一张表中，下一次需要重复计算时直接返回。二、自底向上的递推，可以理解为递推的逆过程，就是从最小的子问题去推导更大的子问题。b5E2R。b5E2R。表示由该点出发往下走的最大价值这题的状态转移方程显然是();(最后一层直接返回该数)B 经典问题。还是思考如何把问题的规模缩小，那么我们首先取两个串各自的第一个或最后一个进行比较，可以进行最优操作（为什么，请思考）。p1Ean。p1Ean。情况一、两者相等，则取之作为最长公共子串，问题就转化为比较 、的最长公共子即可。情况二、两者不相等。则必然舍弃某一个的其中一个字符，再进行接下的比较。问题就转化为与比较，或者是与比较，取大者。DXDiT。DXDiT。表示的前个与的前个的最长公共子串。状态转移方程、 ();();C 经典问题，,最长上升子序列。首先介绍()的方法，对第个数考虑，以找其前一个数为突破口，如果的前一个数为，那么问题就从找前个数的转化成找前个数的。RTCrp。RTCrp。表示前个数的数值 ，那么， ()()的最大的。SixE2。SixE2。K 题意是由多件物品组成最相近的两个数，且物品个数一定。设物品的价值为，有两种方法，一种是背包可以不装满，那么和就是答案。 另一种是将背包装满，只需要从处开始遍历找到的第一个大于的数就是答案。6ewMy。6ewMy。L 很简单的方法是，因为物品可以无限取，那么在背包容量一定的前提下，求费用最小的物品就是答案。还有一种方法就是直接做完全背包，物品价值为。kavU4。kavU4。M 这题也是赤果果的二维费用背包，不理解的再去看背包九讲，注意初始化，即考虑状态的意义，没有意义的状态使之不影响后面的状态。可以在装满的背包中逆序搜经验值大于升级所需，第一个搜到的就是答案。也可以在不装满的背包中搜整张表，经验值大于升级所需，并且所消耗体力最小。y6v3A。y6v3A。N 这题是比较详细的背包问法变化问题，求第大背包。显然记录的状态已经无法满足题目的需要，我们还是要从无后效性（即这个仅根据哪些特征决策）考虑如何描述这个问题，显然，对于每个背包容量都要保存前大的值，这样才能进行状态转移。那么，可以用表示背包容量为的第大价值。显然这个数是由大到小排列的，所以是一个有序序列。那么有这里有两个有序序列和，合并这两个有序序列并将结果（的前项）储存到上，最后的答案就是.M2ub6。M2ub6。O 这题是每组至少取一件的的背包。而分组背包的含义是每组最多取一件，我希望大家在做这题的时候，思路不要被分组背包限制住，虽然和分组背包最大的区别只是把物品遍历的顺序放到第二层上。而用常规状态转移的方式去考虑这个问题。 还是一样，先从无后效性去考虑描述问题的方式。这个问题显然是对于第组物品的状态既可以从第组来也可以从第组来，而分组背包是状态只从组来。（请仔细思考二者的区别）所以需要记录组别来进行状态转移。 于是，我们可以用来表示取到前组物品，背包容量为所能获得的最大价值。0YujC。0YujC。状态转移方程、()至少取一件，所以只能去，要么从第组来，要么从第组来。eUts8。eUts8。P 这题和几乎是一样的，就是赋初值的时候要稍微注意点。（自己思考，就不再赘述了）Q 这题是赤果果的分组背包。详见背包九讲。三层循环。组别、容量、该组物品。（重在理解）R 这题是所选的背包题中最难的一道，也是本背包关的小，这题如果在独立思考的前提下，完全弄懂各种背包的联系区别，并不被其所限，你就可以去拯救世界了。这题的物品组有三种情况，表示的是的至少取一件的背包。表示的是的常规分组背包，表示的其实就是对该组物品做背包。状态描述显然和一样，用来表示取到前组物品，背包容量为所能获得的最大价值。sQsAE。sQsAE。状态转移方程是: (，) ();(); 看着有点烦，但请仔细思考。接下来的问题就是常规的题了，而我们之所以讲了那么多的经典模型，就是为了更熟练地去处理这些常规的问题。GMsIa。GMsIa。这题的思路是先考虑出段被一个邮局覆盖的最短距离和才能进行状态转移，对于这个问题，显然是建在的终点所在的村庄上是最优的，就先不做证明了。这样我们就可以先预处理出任意段被一个邮局覆盖的最短距离和用表示。那么，状态的描述是前个村庄被个邮局覆盖的最短距离和。TIrRG。TIrRG。状态转移方程显然是()（） .这题与最长公共子序列有点类似。都是比较两个串各自的最后一个字符，首先要说明的是向一个串中插入一个字符和向另一个串中删除一个字符其实是一样的，为了便于理解就舍掉插入的操作。显然，状态的描述和最长公共子序列类似，表示的是的前个值转化为的前个值。7EqZc。7EqZc。() 那么要么转化成为前个和前个转化，或者删除其中一种（！） 那么要么，要么删除其中一种于是状态转移方程：()(); ();这题比较难考虑，因为有至少要学分钟这个限制。很自然我们想到状态描述显然是表示前分钟已经睡了分钟。状态转移方程也很容易推：lzq7I。lzq7I。 两种决策，要么睡，要么学习，而学习至少要学分钟，那么 ) (). 这题其实就是求公共最长上升序列，只不过把字符变成字符串。现在的问题是求出了之后，如何输出其中一个方案？ 往回找路径就可以了。有困难的话可以参考以下代码，最好还是独立思考自己完成 。NrpoJ。NrpoJ。()() (); ; ;();这题的难点在于初始化，状态的描述（怎么去思考我就不赘述了，请回忆上课讲过的东西）表示的前个和的前个能否构成的前个，如果可以，赋值为 否则为.1nowf。1nowf。状态转移方程、（）（）;这题的初始化是最重要的地方，请根据以上状态转移方程和状态的实际意义仔细考虑下。状态的描述总是那么明显，表示前个数恰好等于的个数。那么，我们考虑添加一个数，如果放在最后或者是和原来就是的位置交换，那么的个数肯定不边，（思考为什么），如果和原来不是的数进行交换，那么个数（思考）。,这样一来状态转移方程就非常清晰了。fjnFL。fjnFL。(*()(*()这题有点复杂