动规算法两个字符串代价.pdfVIP

编辑两个字符串代价

给定两个字符串str1，str2，在给定三个整数ic,dc,rc，分别代表，删除和替换一个字符

的代价。返回将str1

编辑成str2的代价，比如，str1=abc,str2=adc,ic=5,dc=3,rc=2,从str1到str2，将b换成d

代价最小，所以返回2.

分析：

在构建出动态规划表的时候，关键是搞清楚每个位置上数值的。首先我们生成

dp[M+1][N+1]的动态规划表，M代表str1的长度，N代表str2的长度，那么dp[i][j]就是

str1[0..i-1]变成str2[0...j-1]的最小代价，则dp[i][j]的分别来自以下四种情况：

a、首先将str1[i-1]删除，变成str1[0...i-2],然后将str1[0...i-2]变成str2[0...j-1],那么dp[i-1][j]

就代表从str1[0..i-2]到str2[0...j-1]的最小代价，所以：dp[i][j]=dp[i-1][j]+dc;

b、同理也可以是从str1[0...i-1]变成str2[0...j-2]，然后在str2[j-1],dp[i][j-1]就代表从

str1[0...i-1]变成str2[0...j-2]的最小大家，所以：dp[i][j]=dp[i][j-1]+ic;

c、如果str[i-1]==str2[j-1],则只需要将str1[0...i-2]变成str2[0...j-2]，此时dp[i][j]=dp[i-1][j-1];

d、如果str1[i-1]!=str2[j-1],则我们只需要将str1[i-1]替换成str2[j-1],此时dp[i][j]=

dp[i-1][j-1]+rc;

在这四种情况当中，我们选取最小的一个，即为最小代价。

#includeiostream

#includestring

#includealgorithm

#includevector

usingnamespacestd;

intmain(){

stringstr1=ab12cd3;

stringstr2=abcdf;

//cinstr1;

//cinstr2;

constintM=str1.length();

constintN=str2.length();

//vectorintp(M+1,0);

//vectorvectorintdp(N+1,p);

intdp[10][10]={};

intic=5,dc=3,rc=2;

//intic=1,dc=1,rc=1;

dp[0][0]=0;

for(inti=1;iN+1;i++)

dp[0][i]=ic*i;

for(inti=1;iM+1;i++)

dp[i][0]=dc*i;

for(inti=0;i