最长公共子序列

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int n = s1.size(), m = s2.size();
        vector<vector<int>> f(n + 1,vector<int>(m + 1));

        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);
            }

        if(f[n][m] == 0) return "-1";
        // 最长公共子序列记录方案
        string res;
        int i = n,j = m;
        while(f[i][j] > 0){ // 记录方案，记录转移状态，这里记录最前面，也就是第一个可以转移的
            while(f[i - 1][j] == f[i][j]) i --; // 12C4B6
            while(f[i][j - 1] == f[i][j]) j --;
            res += s1[i - 1]; // i从下标1开始，所以要-1
            i --,j -- ;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};