c++贪心算法解决最长公共子序列长度问题，求两个字符串的最长公共子序列长度

最长公共子序列（Longest Common Subsequence，LCS）问题是一类经典的字符串匹配问题，它的解决方法可以使用动态规划或贪心算法。

下面是使用贪心算法解决最长公共子序列长度问题的思路：

1. 对于两个字符串s1和s2，从两个字符串的开头开始扫描。

2. 如果当前字符相同，那么将两个字符串都向后移动一个字符，即i=i+1，j=j+1。

3. 如果当前字符不同，那么需要考虑哪个字符串的当前字符可以被舍弃，从而尽可能找到更多的共同字符。这里采用的是贪心策略，即选择当前字符匹配次数较多的字符串的当前字符，将其舍弃。

4. 最后，计算出舍弃的字符数，即为最长公共子序列长度。

下面是C++代码实现：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1010;

int f[N][N];

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (s1[i - 1] == s2[j - 1])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m] << endl;

    return 0;
}

其中，f[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列长度。状态转移方程为：

f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1]+(s1[i-1]==s2[j-1]))

时间复杂度为O(nm)，空间复杂度为O(nm)。