大家好，我是小风哥。今天的文章将开启动态规划的话题。动态规划是算法中最重要的思想之一。今天的主题是最短公共超序列。如果一个字符串s删除一些字符后形成t，那么我们说s是t的超序列。现在给定两个字符串str1和str2，返回str1和str2中最短的Longpublicsupersequence，如果有多个，则返回任意一个。假设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（最短公共超序列的缩写）：intscs(inti,intj);这个递归函数的意思就是字符串str1[i,str1.length()-1]和字符串str2[j,str2.length()-1]之间最短的publicsupersequence的长度是多少。根据上面的分析和绘制的状态空间树，可以很容易的写出它的递归实现：stringstr1;stringstr2;intscs(inti,intj){//递归出口1：str1为空，supersequence只需要包括str2的其余部分if(i==str1.length())returnstr2.length()-j;//递归出口2：str2已经为空，超序列只需要包含str1的剩余部分if(j==str2.length())returnstr1.length()-i;//如果两个字符串的首字符相同，则当前问题的解等于子问题的解加1if(str1[i]==str2[j])returnscs(str1,i+1,str2,j+1)+1;//否则当前问题的解等于两个子问题中较小的一个加1returnmin(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)种组合。重复子问题，然后观察上面递归代码形成的状态空间树：这里有一些相同的子问题，这些子问题会被反复计算，所以我们可以记录下子问题的解，当遇到又是子问题有问题直接返回结果即可：stringstr1;stringstr2;vector
