我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划 >

动态规划和数据结构结合的常用优化(1)

归档日期:06-04       文本归类:动态规划      文章编辑:爱尚语录

  定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!NOIP2018冬令营火热报名中!

  动态规划基本会出现在信息学比赛的各类考试中,理解动态规划,学会动态规划的思想对于信息学的同学们来说至关重要!

  【例题1】给定一个长度为n(n = 1000)的字符串A,求插入最少多少个字符使得它变成一个回文串。

  典型的区间模型,回文串拥有很明显的子结构特征,即当字符串X是一个回文串时,在X两边各添加一个字符a后,aXa仍然是一个回文串,我们用d[i][j]来表示A[i...j]这个子串变成回文串所需要添加的最少的字符数,那么对于A[i] == A[j]的情况,很明显有 d[i][j] = d[i+1][j-1] (这里需要明确一点,当i+1 j-1时也是有意义的,它代表的是空串,空串也是一个回文串,所以这种情况下d[i+1][j-1] = 0);当A[i] != A[j]时,我们将它变成更小的子问题求解,我们有两种决策:

  空间复杂度O(n^2),时间复杂度O(n^2), 下文会提到将空间复杂度降为O(n)的优化算法。

  我们发现将d[i][j]理解成一个二维的矩阵,i表示行,j表示列,那么第i行的结果只取决于第i+1和第i行的情况,对于第i+2行它表示并不关心,那么我们只要用一个d[2][N]的数组就能保存状态了,其中d[0][N]为奇数行的状态值,d[1][N]为偶数行的状态值,当前需要计算的状态行数为奇数时,会利用到d[1][N]的部分状态,奇数行计算完毕,d[1][N]整行状态都没用了,可以用于下一行状态的保存,类似“传送带”的滚动来循环利用空间资源,美其名曰 - 滚动数组。

  这是个2D/0D问题,理论的空间复杂度是O(n2),利用滚动数组可以将空间降掉一维,变成O(n)。

  【例题3】给定一个长度为n(1 = n = 1000)的整数序列a[i],求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列),满足如下条件:

  ](它们的状态对应就是d[j] 和 d[k]),如果a[i] a[k],则必然有a[i] a[j],能够选k做决策的也必然能够选 j 做决策,那么如若此时d[j] = d[k],显然k不可能是最优决策(j的决策始终比它优,以j做决策,a[ j ]的值小但状态值却更大),所以d[k]是不需要保存的。

  基于以上理论,我们可以采用二分枚举,维护一个值 (这里的值指的是a[i]) 递增的决策序列,不断扩大决策序列,最后决策的数目就是最长递增子序列的长度。具体做法是:

  枚举i,如果a[i]比决策序列中最大的元素的值还大,则将i插入到决策序列的尾部;否则二分枚举决策序列,找出其中值最小的一个决策k,并且满足a[k] a[i],然后用决策i替换决策k。

  这是个1D/1D问题,理论的时间复杂度是O(n2),利用单调性优化后可以将复杂度将至O(nlogn)。

  给定n个元素(n = 100000)的序列,将序列的所有数分成x堆,每堆都是单调不增的,求x的最小值。

  证明:因为这x堆中每堆元素都是单调不增的,所以原序列的最长递增子序列的每个元素在分出来的每堆元素中一定只出现最多一个,那么最长递增子序列的长度L的最大值为x,所以x = L。

本文链接:http://quangdungfc.net/dongtaiguihua/232.html