题目地址：

https://leetcode.com/problems/shortest-common-supersequence/description/

给定两个字符串$s_1$和$s_2$，求一个字符串$s$，使得$s_1$和$s_2$都是其子序列，并且要求$s$尽可能短。

设$f[i][j]$是$s_1$添加多少个字符可以使得$s_2$为其子序列。设下标都从$1$开始。初始条件$f[0][j]=j$。
1、如果$s_1[i]=s_2[j]$，那么最后一个字母已经相等了，只需要让$s_1$前面添加若干字符即可，所以此时$f[i][j]=f[i-1][j-1]$。
2、如果$s_1[i]\ne s_2[j]$，那么为了使得$s_1$是$s_2$的母序列，必须首先要将$s_2[j]$包含进去，那么有两种可能，第一种是只在$s_1[i]$这个位置之前添加字符，此时$f[i][j]=f[i-1][j]$；第二种是在$s_1[i]$这个位置之后添加字符（之前也有可能添加），那么之后添加的最后一个字符必然等于$s_2[j]$，否则没必要添加，所以此时$f[i][j]=f[i][j-1]+1$。综上 f [ i ] [ j ] = min ⁡ { f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] + 1 } f[i][j]=\min\{f[i-1][j],f[i][j-1]+1\} f[i][j]=min{f[i−1][j],f[i][j−1]+1}。

具体方案可以倒着推，即从$i=m,j=n$开始，如果$s_1[i]=s_2[j]$，那么最优方案就是$f[i-1][j-1]$，只需要$s_1[i]$这个字符；如果$s_1[i]=s_2[j]$则需要分情况，如果$f[i][j]=f[i-1][j]$，则最优方案是在$s_1[i]$之前添加字符，需要将$s_1[i]$加入答案；如果$f[i][j]=f[i][j-1]+1$，则说明需要把$s_2[j]$加入答案。当$i=0$的时候，要将$s_2[j]$所有剩余字符都加入答案。最后将答案反序。代码如下：

class Solution {
 public:
  string shortestCommonSupersequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    s1 = " " + s1;
    s2 = " " + s2;
    int f[m + 1][n + 1];
    memset(f, 0, sizeof f);
    for (int i = 0; i <= n; i++) f[0][i] = i;
    for (int i = 1; i <= m; i++)
      for (int j = 1; j <= n; j++) {
        if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1];
        else f[i][j] = min(f[i - 1][j], f[i][j - 1] + 1);
      }
    
    string res;
    for (int i = m, j = n; i;) {
      if (s1[i] == s2[j]) {
        res.push_back(s2[j--]);
        i--;
      } else {
        if (f[i][j] == f[i - 1][j]) res.push_back(s1[i--]);
        else res.push_back(s2[j--]);
      }
      if (!i) while (j) res.push_back(s2[j--]);
    }
    reverse(res.begin(), res.end());
    return res;
  }
};

时空复杂度$O(l_{s_1}{l}_{s_2})$。