淘宝客网站需要备案,2018年做网站,自已做的网站怎么做域名解析,郑州响应式网站制作首先#xff0c;我们把字符串反转#xff0c;然后用反串和原串求最大公共子序列#xff0c;再用字符串长度减去最大公共子序列的长度就是答案#xff0c;我们还可以用滚动数组优化内存 状态转移方程#xff1a; (i长度的a串和j长度的b串的最长公共子序列长度#xff09; …首先我们把字符串反转然后用反串和原串求最大公共子序列再用字符串长度减去最大公共子序列的长度就是答案我们还可以用滚动数组优化内存 状态转移方程 (i长度的a串和j长度的b串的最长公共子序列长度 1.dp[i-1][j-1]1 a[i]b[j] dp[i][j] 2.max(dp[i][j-1],dp[i-1][j]) a[i]!b[j] #includeiostream
#includecstdio
#includealgorithm
#includecmath
#includecstring
#includestring
using namespace std;
int re[2][1005];//使用滚动数组优化了空间
int main()
{int t,i,j;string a,b;scanf(%d,t);while(t--){cina;ba;reverse(a.begin(),a.end());memset(re,0,sizeof(re));for(i0;ia.length();i)for(j0;jb.length();j){if(a[i]b[j]){re[(i1)1][j1]re[i1][j]1;}else re[(i1)1][j1]re[i1][j1]re[(i1)1][j]?re[i1][j1]:re[(i1)1][j];//条件表达式是最省时间的}printf(%d\n,a.length()-re[(a.length())1][b.length()]);}return 0;
} 转载于:https://www.cnblogs.com/A-way/archive/2013/05/02/3054423.html
