存档

文章标签 ‘动态规划’

百度面试题:POJ 2192 - Zipper

2012年9月30日 8 条评论

---

百度二面的时候有一道题目没有答上来,回来一查,原来是POJ上的原题,是一个DP问题,当时有向这方面想,但始终没有找出重叠子问题,网上看到别人定义的子问题,感觉真心简单,关键看是否能找出子问题了,这个积累不是一时半日的,自己还是太菜。刚刚到POJ上AC了这道题,附题目链接:

POJ 2192: http://poj.org/problem?id=2192

题意:就是给定三个字符串A,B,C;判断C能否由AB中的字符组成,同时这个组合后的字符顺序必须是A,B中原来的顺序,不能逆序;例如:A:mnl,B:xyz;如果C为mnxylz,就符合题意;如果C为mxnzly,就不符合题意,原因是z与y顺序不是B中顺序。

DP求解:定义dp[i][j]表示A中前i个字符与B中前j个字符是否能组成C中的前 (i+j) 个字符,如果能标记true,如果不能标记false;

有了这个定义,我们就可以找出状态转移方程了,初始状态dp[0][0] = 1:

dp[i][j] = 1 如果 dp[i-1][j] == 1 && C[i+j-1] == A[i-1]
dp[i][j] = 1 如果 dp[i][j-1] == 1 && C[i+j-1] == B[j-1]

代码如下:

阅读全文...

动态规划基础回顾

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,等等.

阅读全文...

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] }

阅读全文...