动态规划基础回顾

2012年6月17日 2 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

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

简单背包系列

==01背包==

==完全背包==

==多重背包==

字符串处理

==最长公共子序列==

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

数组相关

==最长递增子序列==

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

面试题

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

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

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

阅读全文...

最长递增子序列(LIS)

2012年6月17日 16 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

最长递增子序列又叫做最长上升子序列;子序列,正如LCS一样,元素不一定要求连续。本节讨论实现三种常见方法,主要是练手。

题:求一个一维数组arr[i]中的最长递增子序列的长度,如在序列1,-1,2,-3,4,-5,6,-7中,最长递增子序列长度为4,可以是1,2,4,6,也可以是-1,2,4,6。

方法一:DP

像LCS一样,从后向前分析,很容易想到,第i个元素之前的最长递增子序列的长度要么是1(单独成一个序列),要么就是第i-1个元素之前的最长递增子序列加1,可以有状态方程:

LIS[i] = max{1,LIS[k]+1},其中,对于任意的k<=i-1,arr[i] > arr[k],这样arr[i]才能在arr[k]的基础上构成一个新的递增子序列。

代码如下:在计算好LIS长度之后,output函数递归输出其中的一个最长递增子序列。

阅读全文...

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

2012年6月13日 4 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

个人认为,大部分情况下,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 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

一个字符串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 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

话说这道题还是三年前径点公司来学院笔试中的一道题目,当时刚进入实验室,师兄在带着我们做新生培训的时候做过这道题,最近回顾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,问题规模都缩小了很大一块。

阅读全文...

面试题:从给定的N个正数中选取若干个数之和最接近M

2012年6月11日 5 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

这道题跟捞鱼问题一样,都是刚进实验室新生培训那会儿做过的题目,不过这个是一师姐当时找工作的面试题。

如题,并输出该子序列

测试用例:2,9,5,7,4,11,10

分别输出最接近33、40、47、60的子序列

分析:N个数之和接近M,将M看做一个容量的背包,这个题目就变成了典型的01背包,M容量下求最优解并输出最优方案,这在01背包中都整理过,上代码:

阅读全文...

多重背包

2012年6月11日 6 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

前面已经回顾了01背包完全背包,本节回顾多重背包的几种实现形式,主要有以下几方面内容:

==多重背包问题定义 & 基本实现

==多重背包二进制拆分实现

==防火防盗防健忘

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

多重背包问题定义 & 基本实现

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

对于多重背包的基本实现,与完全背包是基本一样的,不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。状态转移方程如下


f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=n[i] }

代码与完全背包的区别仅在内部循环上由


for(k = 1; k <= j/weight[i]; ++k)

变为


for(k = 1; k <=n[i] && k<=j/weight[i]; ++k)

当然,输入上的区别就不说了。

阅读全文...

完全背包

2012年6月11日 5 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

前面回顾了01背包,在此基础上本节回顾完全背包的几种实现形式,主要有以下几方面内容:

==完全背包问题定义 & 基本实现

==完全背包二进制拆分思想

==完全背包使用滚动数组(略)

==完全背包中的逆向思维

==完全背包使用一维数组

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

完全背包问题定义 & 基本实现

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

与01背包不同的是,完全背包每件物体可以放入无限件(只要能放的下),故对于每件物品i,相当于拆分成了v/c[i]件相同的物品,拆分之后物品i就不是放入或不放入的两种情况了,而是放入0件、放入1件、放入2件…等情况了,对于该件物品i,最大价值取放入k件的最大值,故状态转移方程为:


f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=v/c[i] }

各状态的意义不再赘述,上代码,关于复杂度以及每种物品的状态数见代码注释:

阅读全文...

二路归并 & 插入归并 & 原地归并

2012年5月31日 4 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

本节回顾整理归并排序算法常见的几种形式,并实现。一般来讲,我们所说的归并排序都是指二路归并(非多路归并),归并排序很基础,其涉及的分治思想应用也很广泛。这里不赘述基本归并排序的思想。

插入归并

归并排序的时间复杂度为O(nlgn),空间复杂度为O(n);

但是一般来讲,基于从单个记录开始两两归并的排序并不是特别提倡,一种比较常用的改进就是结合插入排序,即先利用插入排序获得较长的有序子序列,然后再两两归并(改进后的归并亦是稳定的,因为插入排序是稳定的)。之所以这样改进是有原因的:尽管插入排序的最坏情况是O(n^2),看起来大于归并的最坏情况O(nlgn),但通常情况下,由于插入排序的常数因子使得它在n比较小的情况下能运行的更快一些,因此,归并时,当子问题足够小时,采用插入排序是比较合适的。

复杂度分析

下面分析下插入归并排序最坏情况下的复杂度:假设整个序列长度为n,当子序列长度为k时,采取插入排序策略,这样一共有n/k个子序列。

子序列完成排序复杂度:最坏情况下,n/k个子序列完成排序的时间复杂度为O(nk)。证明:每个子序列完成插入排序复杂度为O(k^2),一共n/k个子序列,故为O(nk)。

子序列完成合并复杂度:最坏情况下,合并两个子序列的时间复杂度为O(n),一共有n/k个子序列,两两合并,共需要lg(n/k)步的合并,所以这些子序列完成合并的复杂度为O(nlg(n/k))。

所以改进后的插入归并排序的最坏情况的复杂度为O(nk+nlg(n/k)),这里k的最大取值不能超过lgn,显然如果k大于lgn,复杂度就不是与归并一个级别了,也就是说假设一个1000长度的数组,采用插入策略排序子序列时,子序列的最大长度不能超过10。

阅读全文...