题目链接：https://vjudge.net/problem/POJ-1080
参考博客：https://yq.aliyun.com/ziliao/372259
题意：给两个字符串，只含有'A'，'G'，'C'，'T'四个字符，现在根据题目给出的表里面的值，在两个字符串里面增加'-'，使最后的两个字符匹配的值最大，输出最大的值。
思路：开一个二维数组，dp[i][j]表示str1[i]和str2[j]之前的字符相匹配可以得到的最大价值，要确定两个要素，一个是递推公式，一个是初始化的值，首先先推递推公式：
如果str1[i]==str2[j]，那么dp[i][j]=max(dp[i][j]，dp[i-1][j-1]+5)；
如果不相等，那么接下来可以分成三种情况：（假设用mp[a]表示字符a对应的数组下标）
1.str1[i]和一个'-'匹配，那么dp[i][j]=max(dp[i][j],dp[i-1][j]+value[ mp[ str1[i] ] ] [ mp['-'] ])；
2.str2[j]和一个'-'匹配，那么dp[i][j]=max(dp[i][j],dp[i][j-1]+value[ mp[ '-'] ] [ mp[ str2[j] ] ])；
3.str1[i]直接和str2[j]匹配，那么dp[i][j]=max(dp[i][j],dp[i-1][j-1]+value[ mp[ str1[i] ] ] [ mp[ str2[j] ] ])；
然后就要确定初始值了，对于dp[0][0]，肯定是等于0，而dp[i][0]，就是dp[i][0]=dp[i-1][0]+value[ mp[ str1[i] ]][ mp['-'] ]；dp[0][j]也是一样，其他的dp[i][j]就赋无穷小就可以了。声明一下，这不是我想出来的，我脑瓜子还是不行。
我的代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 1005 map<char,int>mp; int n,m,k,t; int dp[205][205]; char str1[105],str2[105]; int value[5][5]={{5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},{-1,-2,-2,5,-1},{-3,-4,-2,-1,0}}; void init() { mp['A']=0; mp['C']=1; mp['G']=2; mp['T']=3; mp['-']=4; } int main() { init(); scanf("%d",&t); while(t--){ scanf("%d %s",&n,str1+1); scanf("%d %s",&m,str2+1); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=-INF; } } dp[0][0]=0;//设为0 for(int i=1;i<=n;i++){//初始化 dp[i][0]=value[mp[str1[i]]][4]+dp[i-1][0]; } for(int i=1;i<=m;i++){ dp[0][i]=value[4][mp[str2[i]]]+dp[0][i-1]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(str1[i]==str2[j]) dp[i][j]=max(dp[i-1][j-1]+5,dp[i][j]); else { dp[i][j]=max(dp[i-1][j]+value[mp[str1[i]]][4],dp[i][j]); dp[i][j]=max(dp[i][j-1]+value[4][mp[str2[j]]],dp[i][j]); dp[i][j]=max(dp[i-1][j-1]+value[mp[str1[i]]][mp[str2[j]]],dp[i][j]); } } } printf("%d ",dp[n][m]); } return 0; }