题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //f[i][j]表示text1中前i个，text2中前j个元素的最长长度
        /*分四类
        if(第i个元素和第j个元素相等)  f[i][j] = f[i - 1][j - 1] + 1     
        else if (第i个元素在子序列，第j个元素不在)  f[i][j - 1] (包含了第四种情况)
                (第i个元素不在子序列，第j个元素在)  f[i - 1][j] (包含了第四种情况)
                (第i 第j个元素都不在子序列) f[i][j] = f[i - 1][j - 1]
        */
        int n = text1.size() , m = text2.size();
        //int f[n+1][m+1];
        vector<vector<int>> f(n+1,vector<int>(m+1));
        // 初始化f[0][0] = 0
        for(int i = 1 ; i <= n; i++){
            for(int j = 1 ; j <= m ; j++){
                if(text1[i - 1] == text2[j - 1]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }else{
                    f[i][j] = max(f[i][j - 1] , f[i - 1][j]);
                }
            }
        }

        return f[n][m];
    }
};