存档

文章标签 ‘DP’

最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

2012年6月27日 1 条评论

---

最近练手,整理了一个“最”系列的主题,这些题目有点绕,个别的还有别名(详见博文),混在一块比较乱,就索性放在一起做了个整理,区别的时候要注意子序列与子串的不同,前者不要求连续,后者要求连续;由于大部分跟DP有关,有的还可以渐进寻求多种解法,可以用来做不错的练手。

下面是这些问题的博文目录

==========================

=1=最长公共子序列(LCS)==

=2=最长公共子串==

=3=最长重复子串==

=4=最长不重复子串==

=5=最长回文子串==

=6=最长递增子序列(LIS)==

=7=最大子数组和(连续子数组最大和)==

==========================

总结:

  1. 问题分类
    • 前两个是关于两个字符串的问题、中间三个是关于单个字符串的问题,最后两个是数组相关的问题;不过不一定绝对,例如最长公共子序列也可以是数组问题;
    • 从解决方案看,12属于“二维”DP问题,因为是两个对象间的问题;467属于“一维”DP问题,是单个对象的问题;345又是后缀数组的典型应用。
  2. 为练手,对大多数问题,尽量逐步探索,整理了多种思路,例如在最长不重复子串问题中,我逐步优化,尝试了四种实现方法,并成功得到了时间为O(N),辅助空间为常数的方案,回头反思,发现其优化的思维得益于对最大子数组和以及LIS的整理与思考。
  3. 这些问题之间相互有很多相通的地方,例如,在最长不重复子串问题中,其DP思路与最长递增子序列有点类似,二者同属“一维”的问题,并且都需要记录当前元素“之前”的某些信息;而在DP优化过程中,最长不重复子串问题又与最大子数组和的优化同出一辙,这两个“一维”的DP问题都只使用O(1)的空间便可以记录子问题的最优解,这种“便捷”的方案并不是空穴来风,而是先通过“规规矩矩”的DP一步步探索,才发现这种“trick”的存在,很是有意思。

勘误:

  • 本系列文章所有代码出现 char xx  [256] 的地方改为 int xx [256] ,因为从逻辑上讲char xx[256] 是有可能出问题的。(感谢HFC

阅读全文...

最长不重复子串

2012年6月25日 20 条评论

---

题:从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度并输出一条最长不重复子串。

本节从最直接的方法逐步优化,渐进探索了四种实现方式,并最终找到时间复杂度为O(N),辅助空间为常数的方案,内容如下:

==基本算法 使用Hash==

==DP方案==

==DP + Hash 方案==

==DP + Hash 优化方案==

==================================

基本算法 使用Hash

要求子串中的字符不能重复,判重问题首先想到的就是hash,寻找满足要求的子串,最直接的方法就是遍历每个字符起始的子串,辅助hash,寻求最长的不重复子串,由于要遍历每个子串故复杂度为O(n^2),n为字符串的长度,辅助的空间为常数hash[256]。代码如下:

阅读全文...

动态规划基础回顾

2012年6月17日 2 条评论

---

这些日子在家病着,回顾了动态规划(DP)的一些基础,主要是以一些经典的基础题目为线索,整理一下思路。为了练手,每一个主题都尽量整理了多种实现方式(包括书上、网络上的方法),并做简单的对比。相关文章目录如下,以后碰到其他相关的再慢慢更新吧。

简单背包系列

==01背包==

==完全背包==

==多重背包==

字符串处理

==最长公共子序列==

==字符串相似度(编辑距离)==

数组相关

==最长递增子序列==

==最大子数组和(最大子序列和 | 连续子数组最大和)==

面试题

==面试题:捞鱼问题==

==笔试:子序列和最接近数M==

================================

阅读全文...

字符串相似度(编辑距离)

2012年6月13日 4 条评论

---

个人认为,大部分情况下,DP寻找子问题还是“从后向前”比较直观一些,像这道题目,个人觉得《编程之美》对它的分析就有些别扭,它“从前向后”寻求的子问题使得状态转移矩阵的初始化变得不太方便,不过“从后向前”分析和从前向后效果和原理都是一样的,本节通过三种实现方式来加深理解。

定义字符串的相似度有很多种度量,像前面说的最长公共子序列就是其中的一种,本节所说的“编辑距离”也算是一种,简单来说,编辑距离就是将两个字符串变成相同字符串所需要的最小操作次数。所需的操作可能有:

  1. 修改一个字符(如把“a”替换为“b”)
  2. 增加一个字符(如把“abdd”变为“aebdd”)
  3. 删除一个字符(如把“travelling”变为“traveling”)

例如,对于“abcdefg”和“abcdef”两个字符串来讲,可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的“编辑距离”。如何计算两个字符串的“编辑距离”?

鉴于DP自底向上求解子问题的性质,我们还是对字符串从后向前分析,这样寻找编辑距离的子问题比较直观,而且分解的子问题使得递归做备忘录变得容易理解,也使得自底向上实现时对状态转移矩阵的初始化更为简便易懂。

寻找子问题时,我们完全可以像分析最长公共子序列那样分析这个问题,我觉得它们是灰常相似的,都是“从后向前”看,假设有两个串X=abcdaex,Y=fdfax,它们的最后一个字符是相同的,只要计算X[1,…,6]=abcdae和Y[1,…,4]=fdfa的距离就可以了;但是如果两个串的最后一个字符不相同,那么就可以进行如下的操作来达到目的(xlen和ylen是X串和Y串的长度):

阅读全文...

最长公共子序列(Longest-Common-Subsequence,LCS)

2012年6月12日 6 条评论

---

一个字符串S,去掉零个或者多个元素所剩下的子串称为S的子序列。最长公共子序列就是寻找两个给定序列的子序列,该子序列在两个序列中以相同的顺序出现,但是不必要是连续的。

例如序列X=ABCBDAB,Y=BDCABA。序列BCA是X和Y的一个公共子序列,但是不是X和Y的最长公共子序列,子序列BCBA是X和Y的一个LCS,序列BDAB也是。

寻找LCS的一种方法是枚举X所有的子序列,然后注意检查是否是Y的子序列,并随时记录发现的最长子序列。假设X有m个元素,则X有2^m个子序列,指数级的时间,对长序列不实际。

使用动态规划求解这个问题,先寻找最优子结构。设X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为两个序列,LCS(X,Y)表示X和Y的一个最长公共子序列,可以看出

  1. 如果xm=yn,则LCS ( X,Y ) = xm + LCS ( Xm-1,Yn-1 )。
  2. 如果xm!=yn,则LCS( X,Y )= max{ LCS ( Xm-1, Y ), LCS ( X, Yn-1 ) }

LCS问题也具有重叠子问题性质:为找出X和Y的一个LCS,可能需要找X和Yn-1的一个LCS以及Xm-1和Y的一个LCS。但这两个子问题都包含着找Xm-1和Yn-1的一个LCS,等等.

阅读全文...

有趣的笔试题:捞鱼问题

2012年6月12日 2 条评论

---

话说这道题还是三年前径点公司来学院笔试中的一道题目,当时刚进入实验室,师兄在带着我们做新生培训的时候做过这道题,最近回顾DP的一些基础,翻找以前写的程序,发现了这道题,就贴一下,给出两种方法的代码,并对比了它们在不同规模问题下的效率。

题目:20个桶,每个桶中有10条鱼,用网从每个桶中抓鱼,每次可以抓住的条数随机,每个桶只能抓一次,问一共抓到180条的排列有多少种 (也可求概率)。

分析:我们要在20个桶中一共抓取180条鱼,每个桶能抓到鱼的条数为0-10,仔细想下,这个问题是可以分解成子问题的:假设我们在前i个桶中抓取了k(0<=k<=10*i)条鱼,那么抓取180条鱼的排列种数就等于在剩下的(20-i)个桶中抓取(180-k)条鱼的方法加上前i个桶中抓取k条鱼的方法。

例如,在第一个桶中抓取了2条鱼,那么总的排列数等于在剩下19个桶中抓取178条鱼的排列种数;如果在第一个桶中抓取了10条鱼,那么总的排列数等于在剩下19个桶中抓取170条鱼的排列数,,,依次分解该问题,总的排列数就等于所有这些排列数的总和。有点DP的感觉。

换个思维,在实现上这个题目可以有更为简洁的方法,我们看看这个问题的对偶问题,抓取了180条鱼之后,20个桶中剩下了20条鱼,不同的抓取的方法就对应着这些鱼在20个桶中不同的分布,于是问题转化为将20条鱼分到20个桶中有多少中不同的排列方法(这个问题当然也等价于180条鱼分到20个桶中有多少种不同的方法)?其中,每个桶最多放10条,最少放0条。这样一转化,无论是用搜索还是DP,问题规模都缩小了很大一块。

阅读全文...

0-1背包

2012年4月30日 3 条评论

---

四月份还没写,不能这么荒废了呀,赶紧水一篇吧,哈哈。前些日子回顾了DP的一些基础,就做一下整理吧,从0-1背包开始。

本节回顾0-1背包的基本模型,关于它的实现有很多种写法,这里对不同实现做个简单列举,主要是写代码练手了,主要有以下几方面内容:

==0-1背包问题定义 & 基本实现

==0-1背包使用滚动数组压缩空间

==0-1背包使用一维数组

==0-1背包恰好背满

==0-1背包输出最优方案

========================================

0-1背包问题定义 & 基本实现

问题:有个容量为V大小的背包,有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品,每种物品只有一个,想计算一下最多能放多少价值的货物。

DP的关键也是难点是找到最优子结构和重叠子问题,进而找到状态转移方程,编码就相对容易些。最优子结构保证每个状态是最优的,重叠子问题也即n状态的求法和n-1状态的求法是一样的;DP在实现上一般是根据状态转移方程自底向上的迭代求得最优解(也可以使用递归自顶向下求解)。

回到0-1背包,每个物体i,对应着两种状态:放入&不放入背包。背包的最优解是在面对每个物体时选择能够最大化背包价值的状态。0-1背包的状态转移方程为


f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }

阅读全文...