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

《hduwebdiy25道动态规划题的解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HDUWebDIY25道动态规划题的解题报告（有详细的思路，状态的描述，以及状态转移方程，但不会给出代码，请自己编码）http://acm.hdu.edu.cn/webcontest/contest_show.php?cid=1264密码：zafuA．最简单的dp，但很重要。说明了动态规划产生的动机之一：递归产生的大量重复子问题。有两种解决方法，一、记忆化搜索，就是在用递归处理问题的过程中把已经算过的状态记录在一张表dp[][]中，下一次需要重复计算时直接返回。二、自底向上的递推，可以理解为递推的逆过程，就是从最

2、小的子问题去推导更大的子问题。dp[i][j]表示由该点i,j出发往下走的最大价值这题的状态转移方程显然是dp[i][j]=max(dp[i+1][j],dp[i+1][j+1]);(最后一层直接返回该数)B．dp经典问题LCS。还是思考如何把问题的规模缩小，那么我们首先取两个串各自的第一个或最后一个进行比较，可以进行最优操作（为什么，请思考）。情况一、两者相等，则取之作为最长公共子串，问题就转化为比较len1-1、len2-1的最长公共子即可。情况二、两者不相等。则必然舍弃某一个的其中一个字符，再进行接下的比较

3、。问题就转化为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;ElseDp[i][j]=max(dp[i][j-1],dp[i-1][j]);A．Dp经典问题，LIS,最长上升子序列。首先介绍O(n^2)的方法，对第i个数考虑，以找其前一个数为突破口，如果i的前一个数为j，那么问题就从找前i个数的LIS转化成找前j个数的L

4、IS。Dp[i]表示前i个数的LIS数值，那么，Dp[i]=min{dp[j]

5、(a[j]=d[j]&&d[i]

6、我们可以用二分法对其进行更新，那么更新到n时这个数组的长度，就是答案（请思考）。A．还是和最长上升子序列类似，而这题只需要用O(N^2)的复杂度就可以解决。Dp[i]表示前i个数的最大递增和。状态转移方程、Dp[i]=max(dp[j]+a[i]

7、(a[i]>a[j])&&1=

8、个新的段。状态转移方程为、Dp[i]=max(dp[i-1]+a[i],a[i]);由状态转移方程可以发现，其实和前面连续还是取自身只要判dp[i-1]是否大于0就可以，至于起始位置和终止位置，自己去模拟。C．求最大矩阵和。很暴力的方法就是取出每个矩阵，得出最大值，显然是会超时的。那么，我们能不能利用05的结论做一些变化？如果a[j]表示前i行第j列的和的话，我们对a数组求最大连续子段和，其结果其实就是矩阵成都为i行里的最大矩阵和（好好理解）。那么，我们只要取一个起始（1-n），取矩阵的长度（1-n）求最大连续子

9、段和O（n），也就是说用O（n^3）的复杂度就可以处理这个问题。A．6-18道就都是背包问题，大家好好理解背包九讲，里面说的很清楚，那么，对于接下来的题目，如果是只是照搬背包九讲的结论，我就不详细解释了，对于有特点的题，还是会给出思路,关于初始化的问题，背包九讲里也有，我就不赘述了。这题是赤果果的01背包题。那么一维的状态转移就是、dp[i]=max(dp[i],dp[i-c[i]]+v[i])逆序遍历B．这题是赤果果完全背包，注意初始化。那么一维的状态转移就是dp[i]=max(dp[i],dp[i-c[i]]

10、+v[i])和01背包一样，但要顺序遍历背包容量。C．这题是赤果果多重背包，好好学习多重背包的转化01背包的二进制数方法。我知道大部分人是直接转化成n件物品的01背包做的。但如果数据量增大的话，就处理不了了，后一种方式在复杂度上有很大优化。D．这题比较灵活，我详细说一下。很自然，我们会想到以概率作为背包容量，但以小数做为背包容量显然是不现实的，就算扩大它的倍数转化为整数，