HDU25道动态规划题解题报告.docVIP

HDU 25道动态规划题的解题报告 （有详细的思路，状态的描述，以及状态转移方程，但不会给出代码，请自己编码）  HYPERLINK /webcontest/contest_show.php?cid=1264 /webcontest/contest_show.php?cid=1264 密码：zafu 最简单的dp，但很重要。说明了动态规划产生的动机之一：递归产生的大量重复子问题。有两种解决方法，一、记忆化有哪些信誉好的足球投注网站，就是在用递归处理问题的过程中把已经算过的状态记录在一张表dp[][]中，下一次需要重复计算时直接返回。二、自底向上的递推，可以理解为递推的逆过程，就是从最小的子问题去推导更大的子问题。 dp[i][j]表示由该点i,j出发往下走的最大价值 这题的状态转移方程显然是 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1]);(最后一层直接返回该数) dp经典问题LCS。还是思考如何把问题的规模缩小，那么我们首先取两个串各自的第一个或最后一个进行比较，可以进行最优操作（为什么，请思考）。 情况一、两者相等，则取之作为最长公共子串，问题就转化为比较len1-1 、len2-1的最长公共子即可。 情况二、两者不相等。则必然舍弃某一个的其中一个字符，再进行接下的比较。问题就转化为len1与len2-1比较，或者是len1-1与len2比较，取大者。 dp[i][j]表示str1的前i个与str2的前j个的最长公共子串。 状态转移方程、 If(str1[i-1]==str2[j-1]) Dp[i][j]=dp[i][j]+1; Else Dp[i][j]=max(dp[i][j-1],dp[i-1][j]); Dp经典问题，LIS,最长上升子序列。首先介绍O(n^2)的方法，对第i个数考虑，以找其前一个数为突破口，如果i的前一个数为j，那么问题就从找前i个数的LIS转化成找前j个数的LIS。 Dp[i]表示前i个数的LIS数值 ，那么， Dp[i]=min{dp[j] | (a[j]a[i])1=ji}+1 不幸的是O(n^2)是处理不了这题的，于是思考，应该如何进行优化，考虑到问题的稀疏性，即有些子问题对后续的问题是没有帮助的，那么我们就不需要保留它的状态。 如果dp[i]=d[j]d[i]a[j]的话，那么后面的数再进行决策时决不会选j作为它的前一个数，所以j不需要保留。因此需要保留的只是，记为f[i]表示此前最长上升子序列为i的序列最后一个数的最小值。那么显然f[i]是一个递增学列，我们可以用二分法对其进行更新，那么更新到n时这个数组的长度，就是答案（请思考）。 还是和最长上升子序列类似，而这题只需要用O(N^2)的复杂度就可以解决。 Dp[i]表示前i个数的最大递增和。 状态转移方程、 Dp[i]=max(dp[j]+a[i] | (a[i]a[j])1=ji) 求最大连续子段和。先思考对第i个数，我们要根据什么进行决策，是以第i-1个数为结尾的最大连续子段和，那么，dp[i]的状态可以描述为以第i个数为结尾最大连续子段和。显然，对于i有两种决策，要么和前i-1个数连续， 要么自己成为一个新的段。 状态转移方程为、 Dp[i]=max(dp[i-1]+a[i],a[i]); 由状态转移方程可以发现，其实和前面连续还是取自身只要判dp[i-1]是否大于0就可以，至于起始位置和终止位置，自己去模拟。 求最大矩阵和。很暴力的方法就是取出每个矩阵，得出最大值，显然是会超时的。那么，我们能不能利用05的结论做一些变化？如果a[j]表示前i行第j列的和的话，我们对a数组求最大连续子段和，其结果其实就是矩阵成都为i行里的最大矩阵和（好好理解）。那么，我们只要取一个起始（1-n），取矩阵的长度（1-n）求最大连续子段和O（n），也就是说用O（n^3）的复杂度就可以处理这个问题。 6-18道就都是背包问题，大家好好理解背包九讲，里面说的很清楚，那么，对于接下来的题目，如果是只是照搬背包九讲的结论，我就不详细解释了，对于有特点的题，还是会给出思路,关于初始化的问题，背包九讲里也有，我就不赘述了。 这题是赤果果的01背包题。那么一维的状态转移就是、dp[i]=max(dp[i],dp[i-c[i]]+v[i]) 逆序遍历 这题是赤果果完全背包，注意初始化。那么一维的状态转移就是dp[i]=max(dp[i],dp[i-c[i]]+v[i])和01背包一样，但要顺序遍历背包容量。 这题是赤果果多重背包，好好学习多重背包的转化01背包的二进制数方法。我知道大部分人是直接转化成n件物品的01背包做的。但如果数据量增大的话，就处理不了了，