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

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

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

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

3、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个数的LIS。Dp[i]表示前i个数的LIS数值，那么，Dp[i]=min{dp[j]

4、(a[j]

5、+1不幸的是O(n^2)是处理不了这题的，于是思考，应该如何进行优化，考虑到问题的稀疏性，即有些子问题对后续的问题是没有帮助的，那么我们就不需要保留它的状态。如果dp[i]>=d[j]&&d[i]

6、Dp[i]表示前i个数的最大递增和。状态转移方程、Dp[i]=max(dp[j]+a[i]

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

8、，自己去模拟。C．求最大矩阵和。很暴力的方法就是取出每个矩阵，得出最大值，显然是会超时的。那么，我们能不能利用05的结论做一些变化？如果a[j]表示前i行第j列的和的话，我们对a数组求最大连续子段和，其结果其实就是矩阵成都为i行里的最大矩阵和（好好理解）。那么，我们只要取一个起始（1-n），取矩阵的长度（1-n）求最大连续子段和O（n），也就是说用O（n^3）的复杂度就可以处理这个问题。A．6-18道就都是背包问题，大家好好理解背包九讲，里面说的很清楚，那么，对于接下来的题目，如果是只是照搬背包九讲的结论，我就不详细解释了，对于有特点的题，还是会给

9、出思路,关于初始化的问题，背包九讲里也有，我就不赘述了。这题是赤果果的01背包题。那么一维的状态转移就是、dp[i]=max(dp[i],dp[i-c[i]]+v[i])逆序遍历B．这题是赤果果完全背包，注意初始化。那么一维的状态转移就是dp[i]=max(dp[i],dp[i-c[i]]+v[i])和01背包一样，但要顺序遍历背包容量。C．这题是赤果果多重背包，好好学习多重背包的转化01背包的二进制数方法。我知道大部分人是直接转化成n件物品的01背包做的。但如果数据量增大的话，就处理不了了，后一种方式在复杂度上有很大优化。D．这题比较灵活，我详细

10、说一下。很自然，我们会想到以概率作为背包容量，但以小数做为背包容量显然是不现实的，就算扩大它的倍数转化为整数，但小数一旦很