题意：给定两个字符串 str1 和 str2 ，在两个串中都可以插入空格，使两个串的长度最后相等，然后开始匹配，怎样插入空格由匹配规则得到的值最大。
分析：LCS的变形，dp[i][j]表示str1[1...i]和str2[1...j]两个子串的最大匹配值。与lcs类似可以分3个方向对其进行状态转移：
①由dp[i-1][j-1]转移过来，意味着str1[i]和str2[j]进行匹配，新增代价是str1[i]和str2[j]的匹配值。
②由dp[i-1][j]转移过来，意味着str1[1...i-1]和str2[1...j]已经进行过匹配，str1[i]只能和空字符匹配，新增代价是str1[i]和空字符的匹配值。
③由dp[i][j-1]转移过来，与②类似。
得到状态转移方程：
dp[i][j] = max(dp[i - 1][j - 1] + match[str1[i]][str2[j]], max(dp[i - 1][j] + match[str1[i]][' '], dp[i][j - 1] + match[str2[j]][' ']));
代码如下：
#include <iostream> #include <fstream> #include <string> #include <cstring> #include <algorithm> using namespace std; int match[256][256]; int dp[110][110]; char str1[110], str2[110]; void init() { match['A']['A'] = match['C']['C'] = match['G']['G'] = match['T']['T'] = 5; match['A']['C'] = match['C']['A'] = match['A']['T'] = match['T']['A'] = match['T'][' '] = match[' ']['T'] = -1; match['A']['G'] = match['G']['A'] = match['C']['T'] = match['T']['C'] = match['T']['G'] = match['G']['T'] = match[' ']['G'] = match['G'][' '] = -2; match['C']['G'] = match['G']['C'] = match[' ']['A'] = match['A'][' '] = -3; match['C'][' '] = match[' ']['C'] = -4; } int main() { //fstream cin("test.txt"); int k; cin >> k; init(); while (k--) { memset(dp, 0, sizeof(dp)); int len1, len2; cin >> len1 >> str1+1 >> len2 >> str2+1; dp[0][0] = 0; for (int i = 1; i <= len2; i++) dp[0][i] = dp[0][i - 1] + match[str2[i]][' ']; //注意这里一定要加上前一项 for (int i = 1; i <= len1; i++) //因为计算的是前i个字符和空字符的匹配值 dp[i][0] = dp[i - 1][0] + match[str1[i]][' ']; for (int i = 1; i <= len1; i++) for (int j = 1; j <= len2; j++) { //dp[i][j] = dp[i - 1][j - 1] + match[str2[i - 1]][str1[j - 1]]; dp[i][j] = max(dp[i - 1][j - 1] + match[str1[i]][str2[j]], max(dp[i - 1][j] + match[str1[i]][' '], dp[i][j - 1] + match[str2[j]][' '])); } cout << dp[len1][len2] << endl; } //system("pause"); return 0; } 需要注意的是我在做这题的时候WA了一次，看了别人的代码才发现是初始化的时候写错了，我想当然地把dp[i][0]和dp[0][j]的值初始化为str1[i]、str2[j]与空字符的匹配值，实际应该是str1[1...i]、str2[1...j]与空字符的匹配值。只能说自己对dp的理解还是不够到位吧。
