T1：子序列相似度
本题难度中等，做法和编辑距离类似，用 dp[i][j] 表示 \(s\) 的长为 \(i\) 的前缀和 \(t\) 的长为 \(j\) 的前缀的最大相似度
初值：
\(dp[0][0] = 0\)
转移：
\( dp[i][j]= \begin{cases} dp[i-1][j]\\ dp[i][j-1]\\ dp[i-1][j-1] + 225-26|s_i-s_j| \end{cases} \)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int dp[3005][3005];
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
rep(i, n)rep(j, m) {
int now = 0;
chmax(now, dp[i][j+1]);
chmax(now, dp[i+1][j]);
chmax(now, dp[i][j]+225-26*abs(s[i]-t[j]));
dp[i+1][j+1] = now;
}
cout << dp[n][m] << '\n';
return 0;
}