子序列问题（动态规划） |
您所在的位置：网站首页 › 最长有序子序列 › 子序列问题（动态规划） |
子序列问题（动态规划）
|
最长公共子序列长度（LCS）
问题描述：求两个字符串的最长公共子序列长度。（子序列不一定是连续的） 分析：设二维数组dp(i, j)是字符str1[i]与str2[j]之前的LCS。给出两个字符串str1和str2，现在假设判断str1[i]和str2[j]两个字符，这样可以分为两种情况： 1.两者相同 2.两者不同 代码： #include using namespace std; const int M = 110; int dp[M][M]; int main() { string str1, str2; cin >> str1 >> str2; memset(dp, 0, sizeof dp); for(int i = 0; i < str1.size(); i++) { for(int j = 0; j < str2.size(); j++) { if(str1[i] == str2[j]) dp[i + 1][j + 1] = dp[i][j] + 1; else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); } } cout > n; for(int i = 0; i < n; i++) cin >> v[i]; for(int i = 0; i < n; i++) { dp[i] = 1; for(int j = 0; j < i; j++) { if(v[j] < v[i]) dp[i] = max(dp[i], dp[j] + 1); } } cout > n; vector dp(n, 1); for(int i = 0; i < n; i++) cin >> v[i]; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { if(v[j] < v[i]) dp[i] = max(dp[i], dp[j] + 1); } } sort(dp.begin(), dp.end()); cout > t; while(t--) { if(t == 0) slove(); else { slove(); cout 0) flag = 1; sum[i] = sum[i -1] + v[i]; } if(!flag) { cout |
【本文地址】
今日新闻 |
推荐新闻 |