我要投搞

标签云

收藏小站

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

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

动态规划经典模型之区间模型(附dp习题)

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

  区间模型的状态表示一般为d[i][j],表示区间[i, j]上的最优解,然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解,逐步扩大区间的范围,最终求得[1, len]的最优解。

  【例题7】给定一个长度为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)的优化算法。

  每一次猜数,如果猜对,就成功。猜错的线,若猜的数大于目标数,另外生命值再减1。机会用完,或者生命值减至-1,表示失败。

  1.先考虑L=0的情况,由于一次都不能猜错,因此只能从1开始,逐个向上猜,总数不能超过G;

  2.若G=L,等价于G=L的情况,因为此时允许猜的次数限制了最大的数,总数为2^G

  3.一般的情况,比如L=1时,可以设想,只能猜错一次的话,这个数不能太大,否则猜错了一点作用也没有,因此要确保即使本次猜错也能在以后的G-1次猜中,这就转化成了(G-1,0)的情况,也就是说必胜的策略应当为先猜G,如果错,则从1~G-1逐次的猜,如果猜对了就转化成了(G-1,1)的情况,他应当再猜G+G-1……对于G=i,L=j的情况也是一样的考虑,可以列出状态转移方程:

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