Dayi Lin, Ph.D.

Data Scientist | Senior Software Engineering Researcher

Tag: 算法

最小编辑距离 算法原理

问题 最小编辑距离 Minimum Edit Distance 关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。 设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。 例如 s1 = “12433” 和 s2 = “1233”; 则可以通过在s2中间插入4得到12433与s1一致。 即 d(s1,s2) = 1 (进行了一次插入操作) 性质 计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“c1″,”c2”) = c1 == c2 ? 0 : 1; 2. d(s1+c1,s2+c2) = min( d(s1,s2)+ c1==c2 ? 0 : 1 , 1 + d(s1+c1,s2), 1 +

LCS(最长公共子序列)

上次在实验室作《从分治到动归 – 最优问题解法》的讲座的时候,举了LCS(最长公共子序列)作为例子: LCS问题 LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。 例如: X={A,B,C,B,D,A,B} Y={B,D,C,A,B,A} 则X和Y的最长公共子序列(之一)是{B,C,B,A} 传统动归解LCS 设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]} 其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”,否则为“0”。 初值:f[i][0]=0 f[0][i]=0 f[1][1] = same(1,1) 这个动归方程乍看可能不好理解。它的思想是这样的。 对于已知f[i][j]的值,要往后拓展,有这两种情况:其末位i和j相同,或不相同。 考虑相同情况。因为i和j相同,它们必然已被记入最长公共子序列的部分。此时要想延长这个公共子序列,只得令i和j都向后移,看看它们后一位是否也相同。这就是f[i][j]+same(i+1,j+1)。 而对于不同情况,有这几种可能: 虽然第i和j位不相同,但i和j+1是相同的。此时要想延长,便是f[i][j+1]的情况。当然也可能i+1和j相同,便是f[i+1][j]的情况。 综上,写成递归式,因为不知道前一个状态的情况,所以便在这三种可能中取最大值。此时f[i][j]变为f[i-1][j-1],f[i][j+1]变为f[i-1][j],f[i+1][j]变为f[i][j-1]。便得到了上面的递归式。而初值很好理解,这里就不赘述了。 不难算出,这个算法的时间复杂度是O(n^2),空间复杂度也是O(n^2),但因为状态只与上一行有关,所以可以将空间复杂度优化至O(n)。

POJ-2240 解题报告

题意简述 输入货币名称以及货币间的汇率(A到B的汇率可能与B到A的不同),判断是否有可能实现套汇(即从某指定货币开始,通过一系列的货币兑换操作,最终换回某货币并实现盈利)。 问题有多组数据,对于每组数据,第一行代表货币类别数量,第二行起的n行为各货币名称;接下来一行是允许的兑换方式总数,而后每行有三个部分,第一个和第三个分别是原始货币和兑换后货币的名称,第二个是汇率。数据的输入以0结束。 对于每组数据,输出是否可能实现套汇(YES或NO)。

POJ-1125 解题报告

题意简述 股票经纪人之间的关系形成了一个有向关系网。每个股票经纪人向与他关联的另一个人传递一条谣言需要花费的时间各不相同。A向B传播谣言耗时并不一定等于B向A传播耗时。某经纪人收到谣言后会同时开始向他所有关联的经纪人传播谣言。给定股票经纪人之间的关系网以及每个经纪人向特定经纪人传播消息的耗时,问谣言从哪个股票经纪人开始传播能最快的使整个网所有人知道该谣言,并输出最短耗时。如果存在某经纪人无论如何无法得知该谣言,输出disjoint。

POJ-1062 解题报告

题意简述 你想娶酋长的女儿,但酋长要求你给一定数额金钱的聘礼。除了金钱外,酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。 例: 最高最低等级差不超过1,共4个物品 酋长的女儿    等级3     要求现金10000元     或甲的物品+8000元     或乙的物品+5000元 甲的物品        等级2     要求现金1000元        或丙的物品+200元 乙的物品        等级2     要求现金3000元        或丙的物品+200元 丙的物品        等级2      要求现金50元 在这个例子中,最少花费方案是:买丙的东西(50)换乙的东西(+200)换酋长女儿(+5000)一共5250元。

POJ-2253 解题报告

题意简述 湖中有N(2<=N<=200)块石头,标号从1到N。青蛙1在石头1上,青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2,它可以经由任意石头组成的路径。在所有可能路径中找出一条路径,使其中最长的一步的长度小于其他路径中最长的一步的长度。 本题可以化简为,点1与点2间存在若干条路径,每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

POJ-1860 解题报告

题意简述 某城市有M(1<=M<=100)个货币兑换站,可以兑换N(1<=N<=100)种货币,每个兑换站只能互换两种货币,且汇率与手续费各不相同。某人初始时手中有V元货币S,问他是否有可能通过货币兑换,在最后换回货币S时实现盈利,有可能则输出YES,否则输出NO。

POJ-3259 解题报告

题意简述 农夫共有F(1≤F≤5)个农场,每个农场有N块田(1 ≤ N ≤ 500)和M条普通无向路(1 ≤ M ≤ 2500),走过这些路需要一定时间。同时还存在W条有向虫洞(1 ≤ W ≤ 200),走这些虫洞可倒流一定时间。问对于各个农场,农夫是否有可能从某点出发,回到原点时时间早于出发时间。每个农场输出一行。可能则输出YES,否则为NO。