题目：给出两个串，每匹配一种有一种权值，求权值最大的匹配串
就是 最长公共子序列的 的思想： 首先对于 i 和 j 来比较， 一种情况是i和j匹配，此时 dp[i][j] = dp[i - 1][j - 1] + g[ str1[i] ][ str2[j] ]，另一种情况是i和j不匹配，那么就有两种情况，一 i 和 j前面的匹配，j与一个空 即 ‘ - ’匹配，dp[i][j] = dp[i ][ j - 1] + g[ ' - ' ][ str2[j] ] ，二 i 前面的 和 j匹配上，此时 i 和 ‘ - ’匹配，dp[i][j] = dp[i - 1][ j] + g[ str1[i] ][ '-' ]，三种情况取最大。
这题就败在了初始化上=_=
第一次只初始化了dp[0][0]，后来将 dp[1][0]和dp[0][1]又初始化了，其实要把 dp【0】【i] 和 dp[i][0] 和 dp【0][0] 都要初始化，这也是很明显的=_=
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int Max = ;
int g[][] = { {, -, -, -, - }, { -, , -, -, - }, { -, -, , -, -} , { -, -, -, , -}, {-, -, -, -, INF} };
map<char, int> m; // 为每一个 字母建立一个映射
int dp[Max][Max];
int main()
{
m['A'] = ;
m['C'] = ;
m['G'] = ;
m['T'] = ;
m['-'] = ;
int T;
scanf("%d", &T);
while (T--)
{
int len1, len2;
char str1[Max], str2[Max];
scanf("%d %s", &len1, str1 + );
scanf("%d %s", &len2, str2 + );
dp[][] = ;
for (int i = ; i <= len2; i++)
dp[][i] = dp[][i - ] + g[][ m[str2[i]] ];
for (int i = ; i <= len1; i++)
dp[i][] = dp[i - ][] + g[ m[str1[i]] ][]; //cout << str1 + 1 << endl;
//cout << str2 + 1 << endl;
for (int i = ; i <= len1; i++)
{
for (int j = ; j <= len2; j++)
{
dp[i][j] = dp[i - ][j - ] + g[ m[str1[i]] ][ m[str2[j]] ];
//if (dp[i - 1][j] + g[ m[str1[i]] ][4] INF)
dp[i][j] = max(dp[i][j], dp[i - ][j] + g[ m[str1[i]] ][]); //其实初始化在这里很明显，因为要用dp[i - 1][j】，当 i= 1时，必须知道所有的 dp[0][j]+_+
//if (dp[i][j - 1] + g[4][ m[str2[j]] ] != INF)
dp[i][j] = max(dp[i][j], dp[i][j - ] + g[][ m[str2[j]] ]);
}
}
printf("%d\n", dp[len1][len2]);
}
return ;
}