文档章节

编辑距离问题 - 经典DP问题

m2012
 m2012
发布于 2012/05/20 20:10
字数 1754
阅读 4518
收藏 0
dp

 

这题必须好好写一下心得。这题包含很多“剪切粘贴”技术,这是一种强化题目条件,并且不会改变问题最终答案的技巧。

 先设A的长度为LA,B的长度为LB,并且第一个字符的编号为1。

 这种类型的dp,经常都是以首尾字符作为突破口的。
我们来看一下A[1],由于最后B是要变成跟A一样的,所以,为了获得一个字符来跟A[1]配对,必然满足其中一个情况:(1) 我们要么插一个字符x(x等于A[1])到B里面去跟A[1]配对,或者使用B本身就有的某个字符B[k](B[k]等于A[1])来跟A[1]配对。

先看情况一,就是 我们插入一个x到B里面去跟A[1]配对。
显然,这个x最简单就是插入到B的最前面,也就是B[1]的前面,然后我们要做的就是 将 B[1....LB] 和 A[2....LA] 变成一样。成功转移!
可是,除了插到B的最前面以外,我们还可以把x插入到B的其他位置啊,不需要考虑一下吗?
这个疑问不是多余的,所以现在就来证明一下:只考虑插入到B的最前面,不考虑插入到B的其他部分,也不会影响最后得到的最优解。
假设存在一个最优方案,是把x插到B[1]后面的某个位置的,譬如说插入到B[3]的前面(B[2]的后面)。那么,当我们插入x到B[3]前面以后,我们要做的就是 把B[1..2]删掉,把B[3....LB] 变成和A[2...LA]一样。我们可以对这个方案实施剪切粘贴,也就是说,当我们把x插入到B[1]前面之后,接下来,我们也可以一样地通过 把B[1..2]删掉,把B[3....LB] 变成和A[2...LA]一样 来实现我们的最终目的——把B变成和A一样!所以,就算我们只考虑把x插入到B[1]的前面,我们最后也肯定不会错过最优解!

再看情况二,就是 我们尝试在B里面找某个B[k]来跟A[1]配对。
最简单的情况就是,如果B[1]恰好等于A[1],那么我们要做的就只是 把B[2...LB]变成和A[2...LA]一样。转移成功。
可是,这里还有个疑问,就算A[1]恰好等于B[1], 但是我们前面说,我们是要找某个B[k]来跟A[1]配对的,可是现在只考虑了用B[1],譬如说,如果B[4]也恰好等于A[1],难道不需要考虑吗?
重施故技,还是使用剪切粘贴的思路来证明:只考虑用B[1]来配对A[1],不考虑其他的B[j],是不会影响最后的最优解的。
在B[1]等于A[1]的前提下,假设存在一个最佳方案,并且该最佳方案使用B[4]来跟A[1]配对,那么就意味着,我们要 把B[1..3]删掉,然后把 B[5...LB]变成和A[2....LA]一样。考虑一下,如果我们使用B[1]来跟A[1]配对,接下来,我们也可以 把B[2....4]删掉,然后把B[5...LB]变成和A[2....LA]一样。注意看,这样做付出的代价,跟 “把B[1..3]删掉,然后把 B[5...LB]变成和A[2....LA]一样” 是一样的!也就是说,当B[1]等于A[1]的时候,就算我们只考虑用B[1]来跟A[1]配对,也肯定不会错过最优解的!

继续看,如果B[1]不等于A[1]呢?那我们就只能找另外一个B[j]来跟A[1]配对了,也就意味着我们必须把B[1]删掉了,然后我们要做的就是 把B[2...LB] 变成和A[1....LA] 一样。转移成功。



通过以上的分析,状态转移的思路就全部出来了。

设f(i,j) 表示 将B[j..LB] 变成 A[i..LA]一样的最优方案的代价,那么我们有:
f(i,j) 为
(1)1 + f(i+1,j)
(2)1 + f(i+1,j+1) ,前提是B[j] == A[i]
(3)1 + f(i,j+1),前提是 B[j] != A[i]
取这三者里的最小者


ps,所谓剪切粘贴技术,就是有时候,我们为了解题,需要一些题目没有给出的额外的强化条件或者约束,于是,我们人为地把这些我们需要的条件加上去,然后,我们要做的就是尝试证明,这些我们自己加上去的东西,不会影响最后的问题答案,不然的话,我们是不能加上这些东西的。常用的手段是,我们可以先假设存在一个原问题的最后答案Ans,然后我们只需要证明,我们加上这些额外条件以后得到的答案,跟Ans是一样的!这个技巧在贪心和DP里面用得尤其多,譬如说,单机调度问题里,就是用了这种思路来消除顺序,消除了顺序,一样不影响最后的答案,并且也让dp顺利进行。

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

今天写代码的时候发现看漏了一种操作,那就是修改某个字符。

 

所以重新写一下。不过这次写得简单些。

对于A[1]来说,要么我们插入一个x等于A[1]到B里面,这种情况上面已经讨论过,不然的话,要么我们用B[1]来跟A[1]配对,要么不用B[1],

如果我们用B[1]来跟A[1]配对,又分两种情况,如果B[1]本身就等于A[1],那么不用修改B[1],不然的话就要修改B[1]为A[1]

如果我们不用B[1]来跟A[1]配对,就意味着B[1]必须被删掉。

 

综上,转移方程为

f(i, j) =
f(i + 1, j) + 1            插入A[1]到B的情况
f(i + 1, j + 1)                      用B[1]来跟A[1]配对,而且B[1]==A[1]
f(i + 1, j + 1) +1                 用B[1]来跟A[1]配对,而且B[1]!=A[1]
f(i, j + 1) + 1                      不用B[1]来跟A[1]配对

 

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

char A[100];
char B[100];
int LA, LB;

int f[105][105];

int dp(int i, int j) {
  int & ans = f[i][j];
  if (ans != -1) return ans;


  if (i == LA + 1 && j == LB + 1) return ans = 0;
  if (i == LA + 1) return ans = LB - j + 1;
  if (j == LB + 1) return ans = LA - i + 1;

  ans = dp(i + 1, j) + 1;
  ans = min(ans, dp(i + 1, j + 1) + (A[i] == B[j] ? 0 : 1) );
  ans = min(ans, dp(i, j + 1) + 1);

  return ans;
}


int main() {
  scanf("%s %s", A + 1, B + 1);
  LA = strlen(A + 1);
  LB = strlen(B + 1);
  for (int i = 0; i < 105; ++i)
    for (int j = 0; j < 105; ++j)
      f[i][j] = -1;

  printf("%d\n", dp(1, 1));
  return 0;
}

© 著作权归作者所有

共有 人打赏支持
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
经典dp问题 矩阵取数以及变形

再次总结一些比较经典的在矩阵中确定一个起始状态和结束状态, 问从起始到结束中走过的数要得到, 问最小(大), 路径输出等问题. 这些问题都可以转化为dp模型来解决. 下面以一些我做过的题进行...

anxdada
2018/04/15
0
0
Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer
2017/12/20
0
0
开源中国翻译频道贡献第三期奖励名单

根据我们之前制定的翻译贡献规则说明,现公布第三期翻译者前 10 名贡献最多的会员,分别是: 请以上获奖会员从我们的图书列表中挑出你中意的一本书,并将书名和你的邮递地址通过站内留言发送...

oschina
2013/07/01
2.5K
18
NOIP2017提高组模拟赛 9 (总结)

NOIP2017提高组模拟赛 9 (总结) 第一题 星星   思路:枚举矩形左上角的x,以及在x轴上的长度(矩形的长),然后单调的往下扫。 第二题 战争   经典的网络流01模型,直接构图,跑一次d...

kekxy
2017/06/23
0
0
动态规划

动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长非降子序列(LIS) 最大乘积子串 Unique Paths Unique Paths II Minimum Path Sum Triangle 最...

廖少少
2017/09/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

高度可配置的 Linux 内存守护程序 Nohang!

部分功能特性 具有良好注释的配置文件,配置方面(配置中有 38 个参数) 可以将 SIGKILL 和 SIGTERM 作为发送给 victim 的信号 支持 zram(使用 mem_used_total 作为触发器) 可定制的监控强...

linuxCool
3分钟前
0
0
开源 java CMS - FreeCMS2.8 数据对象 unit

项目地址:http://www.freeteam.cn/ unit 在使用单位相关标签时,标签会封装unit供页面调用。 属性 说明 id id ismail 是否接收互动信件 name 名称 parid 父单位id isok 是否有效 ordernum 排...

freeteam
11分钟前
0
0
awk

awk awk 是一种编程语言,用于在linux/unix下对文本和数据进行处理。数据可以来自标准输入(stdin)、一个或多个文件,或其它命令的输出。它支持用户自定义函数和动态正则表达式等先进功能,是...

李超小牛子
21分钟前
0
0
扩展资源服务器解决oauth2 性能瓶颈

用户携带token 请求资源服务器 资源服务器拦截器 携带token 去认证服务器 调用tokenstore 对token 合法性校验 资源服务器拿到token,默认只会含有用户名信息 通过用户名调用userdetailsserv...

冷冷gg
53分钟前
21
0
[Git] Git整理(四) git rebase 的使用

概述 在之前总结分支相关内容时说道,合并两个分支的提交可以使用git merge,然而除了这种方式之外,还有一种方式就是使用git rebase,这两种方式的最终结果都相同,但是合并历史却不同;git...

天王盖地虎626
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部