先求LCS，并记录Path，即LCS具体用了哪些位置的字符对应，然后对所有LCS的路径（它可能有很多个LCS）遍历，进行如下处理。

比如：

题目给的样例：

第一种LCS:
AGT(AAG)T( )A(G)GC
|||  3  | 1 | 1 ||
AGT( C )T(G)A(C)GC
3+1+1=5

第二种LCS:
AGT(AA)G(T)A(G)GC
|||  2 | 1 | 1 ||
AGT(CT)G( )A(C)GC
2+1+1=4

即找出所有不对应的块，每次选择最长的块长度累加

把几种LCS最小的找出来就AC了

正确性证明是对于所有的方法，它没有改动的字母必然组成一个公共子序列，如果它不是最长公共子序列，那么它必然真包含于某个LCS，而以这个LCS作为基础一定能得到更少步骤的方法，故最优方法必然是以某一LCS为基础，于是穷举所有LCS，来试试谁最优。

对于楼上的“显然这是不对的”（指直接用最长串减LCS方法）所给出的反例，
我这个也能行。

只有一种LCS:
(A)GT( )
 1 || 1
( )GT(C)
1+1=2

不过应该能有更好方法，毕竟我这个954ms，惭愧！

我觉得在DP方面肯定能有所改进。