解答本题时不能想当然地去找字符串内部对称的位置，而是多考虑几种情况分析解法，尤其是示例输入特别简单且特别有迷惑性的时候，更要小心谨慎。
对于给定的字符串 s，有它的反响字符串 s1，那么一定可以通过在 s 中添加新的字符，使得新的 s1 和 s 相等。求最少应该添加多少个字符。
输入分为两部分，第一行为整数 n，表示字符串长度，第二行输入字符串内容，只包含大小写字母和数字。
示例输入为：
输出最少添加的字符数。
对应的示例输出为：
LCS 问题的暴力解法耗时太多，而且最主要的原因是会大量计算重复情况，可以考虑使用动态规划的思路优化解法。
首先，应该理清动态规划的解法的状态转移公式。不妨设字符串 s1 = C1C2C3 ... Cn(表示 n 个字符) 和字符串 s2 = C1C2C3 ... Cm （表示 m 个字符），有最长公共子序列 s3 = C1C2C3 ... Cp（表示 p 个字符）。那么对于最后一个字母，有：
当 Cn = Cm 时，必定有 Cn = Cm = Cp，则 s1、s2、s3 都去掉最后一个字符后再对余下的字符串求 LCS 当 Cn = Cm 不满足 时，则 s1 或者 s2 中的一个去掉一个最后一个字符，和另一个未去掉字符的求解 LCS，两种情况中更长的字符串是原题的结果。 为了避免重复计算，使用二维数组 int[][] c = new int[s1.length()+1][s2.length()+1] 存储结果，c[i][j] 表示 s1 中到第 i 个字符位置组成的子串和 s2 的到第 j 个字符为止的子串求得的 LCS 问题结果。这样就有状态转移方程：
那么，写成方法求 LCS 问题的通用 Java 代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int lcs ( String str1 , String str2 ) {
int len1 = str1 . length ();
int len2 = str2 . length ();
int c [][] = new int [ len1 + 1 ][ len2 + 1 ];
for ( int i = 0 ; i <= len1 ; i ++) {
for ( int j = 0 ; j <= len2 ; j ++) {
if ( i == 0 || j == 0 ) {
c [ i ][ j ] = 0 ;
} else if ( str1 . charAt ( i - 1 ) == str2 . charAt ( j - 1 )) {
c [ i ][ j ] = c [ i - 1 ][ j - 1 ] + 1 ;
} else {
c [ i ][ j ] = Integer . max ( c [ i - 1 ][ j ], c [ i ][ j - 1 ]);
}
}
}
return c [ len1 ][ len2 ];
}
动态规划加速计算的思路是典型的“空间换时间”，但是如果问题规模过大，可能又会面临内存占用超限制的问题。仔细观察 LCS 问题的状态转译方程可以发现，其实原有的数组 c[i][j] 只依赖 c[i-1][j] 和 c[i][j-1] 项的值，所以为了保证结果正确其实只需要缓存最近的这两次计算结果就好了，也就是说要缓存原有二维数组中的上一行和当前计算元素的左面相邻元素。而新计算的结果又被缓存，以方便下一轮计算。
所以，可以构造一个新的数组，宽度等于原二维数组，但只有两行：一行用于缓存上一轮计算结果，一行用于记录本轮计算结果，每次计算完毕后就更换缓存区和记录区位置。
对于上面的通用解法中的递推内容，可以有如下改变：
1
2
3
4
5
6
7
8
9
10
11
12
13
int d [][]= new int [ 2 ][ len2 + 1 ];
int t = 0 ;
for ( int i = 1 ; i <= len1 ; i ++) {
t = 1 - t ;
for ( int j = 1 ; j <= len2 ; j ++) {
if ( str1 . charAt ( i - 1 ) == str2 . charAt ( j - 1 )) {
d [ t ][ j ] = d [ 1 - t ][ j - 1 ] + 1 ;
} else {
d [ t ][ j ] = max ( d [ 1 - t ][ j ], max [ t ][ j - 1 ]);
}
}
}
这样，缓存计算结果的数组内容不断变化，就好像在不断滚动一样，故称为“滚动数组”。**注意：**滚动数组会降低程序运行效率，需要谨慎使用。
如果只考虑题目中给出的输入情况，会很容易得出错误的思路，即找到字符串中中间的位置，再清单两边不对称的字母的个数。举个最简单的例子 abb 就无法用这个方法求的正确解。
再仔细思考，应知道要加入的字符数量最少，那么就应该尽量多的利用已有的字符串内容构造相等的情况。也就是说原字符串 s 和反转后的字符串 s1 应该有尽量多的相同字符，即最长公共子序列（LCS）。不是最大子串的原因在于，可以在原字符串任意位置添加字符，所以只能是最大子序列。
除了最大子序列外的字符都是需要通过添加字符，调整到对应位置相等的，所以题目的解为原字符串长度减去最大子序列长度。
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
import java.util.Scanner;
public class Main {
private static int max(int a, int b) {
return a > b ? a : b;
}
private static int lcs(String a, String b) {
int len1 = a.length();
int len2 = b.length();
int[][] buf = new int[2][len2 + 1];
int t = 0;
for (int i = 1; i <= len1; i++) {
t = 1 - t;
for (int j = 1; j <= len2; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
buf[t][j] = buf[1 - t][j - 1] + 1;
} else {
buf[t][j] = max(buf[1 - t][j], buf[t][j - 1]);
}
}
}
return buf[t][len2];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String str = in.next();
String rev = new StringBuilder(str).reverse()
.toString();
System.out.println(str.length() - lcs(str, rev));
}
}
【动态规划】最长公共子序列与最长公共子串
滚动数组
