大家好，我是小風哥，今天這篇文章會開啟動態規劃這個主題，動態規劃是算法中非常重要的思想之一。

今天的題目是最短公共超序列，如果一個字符串s在刪除某些字符后形成t，那么我們說s是t的超序列，現在給定兩個字符串str1與str2，返回str1與str2的最長公共超序列，如果有多個的話返回任意一個即可。

假設str1為"abac"，str2為“cab”，那么這兩個字符串的最短公共超序列是“cabac”；而如果str1為“bc”，str2為“cab”，那么最短公共超序列是“cabc”或者“bcab”。

想一想該怎樣解決問題。

子問題與選擇

動態規劃類問題的關鍵在于找出子問題以及子問題與原始問題的關聯，要想找出子問題就需要知道每一步的選擇是什么。

在這個問題中如果str1=“abec”、str2=“aecd”，因為st1與str2的第一個字符相同，那么我們知道字符‘a’一定是最短公共超序列中的一個，這樣str1就變為了“bec”，str2就變為了“ecd”，而這個問題本質上和原始問題沒有區別，就這樣我們找到了子問題。

現在，str1=“bec”和str2=“ecd”的第一個字符不再相等該怎么辦呢？很簡單：

超序列中包含str1的第一個字符，這樣str1就變為了“ec”，str2依然是“ecd”，假設此時str1與str2的最短公共超序列為supers1

超序列中包含str2的第一個字符，這樣str1依然是“bec”，str2就變為了“cd”，假設此時str1與str2的最短公共超序列為supers2

原始問題的最長公共超序列一定是supers1與supers2中最短的那一個。

現在我們找到了原始問題與子問題的關聯。

狀態空間樹

基于上述分析，我們可以很容易的畫出這樣的狀態空間樹：

上圖中每一個方框都代碼一個子問題，如果某個子問題中的兩個字符串的首字符不相等那么會衍生出兩個新的的子問題，超序列要么使用str1的第一個字符，要么使用str2的第一個字符；而如果str1與str2的首字符相同，那么超序列中只需要新增該字符即可。

該狀態空間樹的葉子節點為所有str1與str2都為空，此時經過從根節點到葉子結點一路的選擇我們就得到了其對應的超序列，從上圖看有兩種最短公共超序列“bcab”與“cabc”，長度都是4。

從這棵狀態空間樹中你可以輕易的看到原始問題是如何分解為子問題的以及如果利用子問題的解來構建原始問題的解。

圖中每個方框代表一個子問題，決定子問題的只有兩個元素，str1與str2首字符的在各自對應字符串的起始位置i和j，因此我們定義遞歸函數scs（shortest common supersequence的縮寫）：

int scs(int i, int j);

該遞歸函數的含義是字符串str1[i, str1.length()-1]與字符串str2[j, str2.length()-1]的最短公共超序列的長度是多少。

基于上述分析與畫出的狀態空間樹你可以很容易的寫出其遞歸實現：

string str1;
string str2;

int scs(int i, int j) {
  // 遞歸出口1：str1已經為空，超序列只需要包含str2剩下的部分即可
  if (i == str1.length()) return str2.length() - j;
  
  // 遞歸出口2：str2已經為空，超序列只需要包含str1剩下的部分即可
  if (j == str2.length()) return str1.length() - i;
  
  // 如果兩個字符串的首字符相同，當前問題的解等于子問題的解加1
  if (str1[i] == str2[j]) return scs(str1, i + 1, str2, j + 1) + 1;
  
  // 否則當前問題的解等于兩個子問題解較小的那一個加1
  return min(scs(i + 1, j), scs(i, j + 1)) + 1;
}

可以看到實際上我們只需要四行代碼就可以搞定問題，（注意看該遞歸實現，和最長回文子串這個示例的實現在形式上幾乎完全相同，是不是很有趣）。

在這這里將str1與str2作為全局變量，這樣你可以清楚的看到遞歸函數scs的返回值只依賴于參數i和j，而參數i的取值屬于[0, str1.length()]，j的取值屬于[0, str2.length()]，因此參數i和j的組合最多只有(str1.length() + 1) * (str2.length() + 1) 個。

重復子問題

再來觀察下上述遞歸代碼的形成的狀態空間樹：

這里存在著一些完全相同的子問題，這些子問題會被重復計算，因此我們可以將子問題解記錄下來，當再次遇到該子問題時直接返回結果即可：

string str1;
string str2;
vector<vector<int>> cache;

int scs(int i, int j) {
  if (i == str1.length()) return str2.length() - j;
  if (j == str2.length()) return str1.length() - i;
  if (cache[i][j]) return cache[i][j];

  int res;
  if (str1[i] == str2[j]) 
    res = scs(str1, i + 1, str2, j + 1) + 1;
  else 
    res = min(scs(i + 1, j), scs(i, j + 1)) + 1;
  return cache[i][j] = res;
}

增加cache后每個子問題只被計算一次，這實際上就是遞歸版的動態規劃代碼了。

動態規劃實現

接下來我們著手將自頂向下的遞歸代碼轉為自底向上的動態規劃代碼。

既然子問題的個數就只有這么多，因此可以使用數組dp來保存子問題解，注意看上述遞歸函數只依賴兩個參數，因此數組dp是二維的，即(str1.length() + 1) * (str2.length() + 1)的二維數組：

vector<vector<int>>dp(str1.length() + 1, vector<int>(str2.length() + 1, 0));

接下來就是最小子問題是什么，注意觀察上述兩個遞歸出口，可以看到最小子問題分別是str1與str2為空的情況，基于這兩種情況我們可以很容易的構建出最小子問題解，將遞歸代碼中的：

if (i == str1.length()) return str2.length() - j;
if (j == str2.length()) return str1.length() - i;

轉為：

  for (int j = str2.length() - 1; j >= 0; j--)
    dp[str1.length()][j] = str2.length() - j;

  for (int i = str1.length() - 1; i >= 0; i--)
    dp[i][str2.length()] = str1.length() - i;

最后我們手動利用兩個for循環構造出所有i和j的組合，將遞歸函數中除去遞歸出口的這一部分:

if (str1[i] == str2[j]) return scs(str1, i + 1, str2, j + 1) + 1;
return min(scs(str1, i + 1, str2, j), scs(str1, i, str2, j + 1)) + 1;

直接放到兩個for循環之中，并且將遞歸調用轉為對數組dp的讀寫：

for (int i = str1.length() - 1; i >= 0; i--) {
  for (int j = str2.length() - 1; j >= 0; j--) {
    if (str1[i] == str2[j]) 
      dp[i][j] = dp[i + 1][j + 1] + 1;
    else 
      dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + 1;
  }
}

這樣完整的實現代碼為：

int shortestCommonSupersequence(string str1, string str2) {
  vector<vector<int>>dp(str1.length() + 1, vector<int>(str2.length() + 1, 0));

  for (int j = str2.length() - 1; j >= 0; j--)
    dp[str1.length()][j] = str2.length() - j;

  for (int i = str1.length() - 1; i >= 0; i--)
    dp[i][str2.length()] = str1.length() - i;

  for (int i = str1.length() - 1; i >= 0; i--) {
    for (int j = str2.length() - 1; j >= 0; j--) {
      if (str1[i] == str2[j]) 
        dp[i][j] = dp[i + 1][j + 1] + 1;
      else 
        dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + 1;
    }
  }

  return dp[0][0];
}