大家好，我是小風(fēng)哥，今天這篇文章會(huì)開(kāi)啟動(dòng)態(tài)規(guī)劃這個(gè)主題，動(dòng)態(tài)規(guī)劃是算法中非常重要的思想之一。

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

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

想一想該怎樣解決問(wèn)題。

子問(wèn)題與選擇

動(dòng)態(tài)規(guī)劃類(lèi)問(wèn)題的關(guān)鍵在于找出子問(wèn)題以及子問(wèn)題與原始問(wèn)題的關(guān)聯(lián)，要想找出子問(wèn)題就需要知道每一步的選擇是什么。

在這個(gè)問(wèn)題中如果str1=“abec”、str2=“aecd”，因?yàn)閟t1與str2的第一個(gè)字符相同，那么我們知道字符‘a(chǎn)’一定是最短公共超序列中的一個(gè)，這樣str1就變?yōu)榱恕癰ec”，str2就變?yōu)榱恕癳cd”，而這個(gè)問(wèn)題本質(zhì)上和原始問(wèn)題沒(méi)有區(qū)別，就這樣我們找到了子問(wèn)題。

現(xiàn)在，str1=“bec”和str2=“ecd”的第一個(gè)字符不再相等該怎么辦呢？很簡(jiǎn)單：

超序列中包含str1的第一個(gè)字符，這樣str1就變?yōu)榱恕癳c”，str2依然是“ecd”，假設(shè)此時(shí)str1與str2的最短公共超序列為supers1

超序列中包含str2的第一個(gè)字符，這樣str1依然是“bec”，str2就變?yōu)榱恕癱d”，假設(shè)此時(shí)str1與str2的最短公共超序列為supers2

原始問(wèn)題的最長(zhǎng)公共超序列一定是supers1與supers2中最短的那一個(gè)。

現(xiàn)在我們找到了原始問(wèn)題與子問(wèn)題的關(guān)聯(lián)。

狀態(tài)空間樹(shù)

基于上述分析，我們可以很容易的畫(huà)出這樣的狀態(tài)空間樹(shù)：

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

該狀態(tài)空間樹(shù)的葉子節(jié)點(diǎn)為所有str1與str2都為空，此時(shí)經(jīng)過(guò)從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)一路的選擇我們就得到了其對(duì)應(yīng)的超序列，從上圖看有兩種最短公共超序列“bcab”與“cabc”，長(zhǎng)度都是4。

從這棵狀態(tài)空間樹(shù)中你可以輕易的看到原始問(wèn)題是如何分解為子問(wèn)題的以及如果利用子問(wèn)題的解來(lái)構(gòu)建原始問(wèn)題的解。

圖中每個(gè)方框代表一個(gè)子問(wèn)題，決定子問(wèn)題的只有兩個(gè)元素，str1與str2首字符的在各自對(duì)應(yīng)字符串的起始位置i和j，因此我們定義遞歸函數(shù)scs（shortest common supersequence的縮寫(xiě)）：

int scs(int i, int j);

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

基于上述分析與畫(huà)出的狀態(tài)空間樹(shù)你可以很容易的寫(xiě)出其遞歸實(shí)現(xiàn)：

string str1;
string str2;

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

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

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

重復(fù)子問(wèn)題

再來(lái)觀察下上述遞歸代碼的形成的狀態(tài)空間樹(shù)：

這里存在著一些完全相同的子問(wèn)題，這些子問(wèn)題會(huì)被重復(fù)計(jì)算，因此我們可以將子問(wèn)題解記錄下來(lái)，當(dāng)再次遇到該子問(wèn)題時(shí)直接返回結(jié)果即可：

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后每個(gè)子問(wèn)題只被計(jì)算一次，這實(shí)際上就是遞歸版的動(dòng)態(tài)規(guī)劃代碼了。

動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)

接下來(lái)我們著手將自頂向下的遞歸代碼轉(zhuǎn)為自底向上的動(dòng)態(tài)規(guī)劃代碼。

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

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

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

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

轉(zhuǎn)為：

  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;

最后我們手動(dòng)利用兩個(gè)for循環(huán)構(gòu)造出所有i和j的組合，將遞歸函數(shù)中除去遞歸出口的這一部分:

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;

直接放到兩個(gè)for循環(huán)之中，并且將遞歸調(diào)用轉(zhuǎn)為對(duì)數(shù)組dp的讀寫(xiě)：

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

這樣完整的實(shí)現(xiàn)代碼為：

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