題目大意:
有 a , b 兩個字串求他們的 LCS(最長公共子序列) 最短修改數?
分析:
LCS 與 LCS-less modify
透過此圖可以了解 DP 原理
LCS 遞迴公式:
- LCS(x, y) =
- max( LCS( x-1, y ), LCS( x , y-1 ) ) , when str[x] != str[y]
- LCS( x-1 , y-1 ) + e1 , when str[x] == sty[y]
LCS-less modify(LCS-lm) 遞迴公式:
- LCS-lm( x, y ) =
- min( LCS-lm( x , y ), LCS-lm( x , y) , LCS-lm( x-1 , y-1) ) +1 , when str[x] != str[y]
- LCS-lm( x -1 , y -1 ) +1 , when str[x] == str[y]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
struct LCS{
int step , max_len ;
}Dp[5000][5000];
int main()
{
#ifdef LOCAL
freopen("in1.txt" , "r" , stdin );
#endif
int intX , intY , Min_step , Max_len ;
string strX , strY ;
while(cin >> intX >> strX >> intY >> strY ){
for(int i = 0 ; i <= intY ; i++){
Dp[0][i].max_len = 0 ;
Dp[0][i].step = i ;
}
for(int i = 0 ; i <= intX ; i++){
Dp[i][0].max_len = 0 ;
Dp[i][0].step = i ;
}
Max_len = 0 ;
Min_step = 0 ;
for(int i = 1 ; i <= intX ; i++){
for(int j = 1 ; j <= intY ; j++){
if(strX[i-1] == strY[j-1]){
Dp[i][j].max_len = Dp[i-1][j-1].max_len +1 ;
Dp[i][j].step = Dp[i-1][j-1].step ;
}
else{
Dp[i][j].max_len = max(Dp[i-1][j].max_len , Dp[i][j-1].max_len ) ;
Dp[i][j].step = min( min(Dp[i-1][j-1].step , Dp[i][j-1].step ) , Dp[i-1][j].step ) +1 ;
}
}
}
cout << Dp[intX][intY].step << '\n' ;
}
return 0;
}
|