【动态规划】LeetCode1092. 最短公共超序列_动态规划 最短公共超序列

1092. 最短公共超序列

 给定字符串a，b，求a，b的最短公共超序列，即a，b同时是这个序列的子序列且这个序列最短。

转化位编辑距离的问题

【动态规划】区间dp：编辑距离_暮色_年华的博客-CSDN博客

问题可以转化为：

对a进行添加操作，使得添加后的a包含b，求最少的添加次数。

 解释：

如果想要在a[i]后添加一个字符后做到a包含b，那么必须使a[ 1 ~ i ]包含b[ 1~ j-1 ]，即 在这种情况下  dp[ i ] [ j ] = dp[ i ][ j - 1 ] + 1 。

如果在a[i]后不添加字符就可以做到a包含b，那么当 a[ i ] ! =b[ j ] 时，把a[i]去掉后a依然可以包含b[j]，所以在这种情况下，dp[ i ][ j ] = dp[ i-1 ][ j ]

当a[ i ] = = b [ j ] 时 ， 可以 不用 a[ i ]取匹配 b[ j ]，dp[ i ][ j ]=dp[ i -1 ][ j ],也可以用a [ i ] 去匹配

b[ j ]，dp[ i ][ j ]=dp[ i-1 ][ j- 1]

？用for循环逆序输出结果。

class Solution {
public:
    string shortestCommonSupersequence(string a, string b) {
        int n = a.size(), m = b.size(), INF = 1e8;
        vector<vector<int>> f(n + 1, vector<int>(m + 1, INF));
        for (int i = 0; i <= n; i ++ ) f[i][0] = 0;
        for (int i = 1; i <= m; i ++ ) f[0][i] = i;
 
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j]);
                if (a[i - 1] == b[j - 1])
                    f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            }
 
        string res;
        for (int i = n, j = m; i >= 0;) {
            if (!i || !j || a[i - 1] != b[j - 1]) {
                if (j && f[i][j] == f[i][j - 1] + 1) {
                    res += b[ -- j];
                } else {
                    if (i) res += a[ -- i];
                    else i -- ;
                }
            } else {
                if (f[i][j] == f[i][j - 1] + 1) {
                    res += b[ -- j];
                } else if (f[i][j] == f[i - 1][j]) {
                    res += a[ -- i];
                } else {
                    res += a[ -- i];
                    j -- ;
                }
            }
        }
 
        reverse(res.begin(), res.end());
        return res;
    }
};