算法基础：动态规划（二）   算法基础:动态规划（二） 关于动态规划，这里再举一个书上的经典例子。 求最长公共子序列（LCS） 问题描述： 令序列X=x1x2x3...xm ，序列 Y=y1y2...yk 是X 的子序列，存在X 的一个严格递增下标序列<i1,i2,...,ik>，使得对于所有的j=1,2,...,k有xij=yj。例如，X=ABCBDAB,Y=BCDB，则Y是X的一个子序列。 给定两个序列X和Y，称序列Z是和X和Y的公共子序列，是指Z同时是X和Y的组序列。最长公共子序列问题定义为：给定序列X=x1x2...xm和Y=y1y2...yn，求这两个序列的最长公共子序列 。以X=ABCBDAB,Y=BCDB为例，两者的公共子序列为Z=BCDB。 问题分析： 如果是匹配字符串问题的话，可以用经典KMP算法，可惜不是，求不得。如果使用暴力算法，穷举X的所有子序列，并与Y序列比较，其时间复杂度可以达到O(2mn)，对于长序列来说，这个代价是不可接受的。那我们使用动态规划按照以下步骤来解决这个问题: 1）刻画最长公共子序列问题的最优子结构。 设X=x1x2...xm和Y=y1y2...yn是两个序列，Z=z1z2...zk是X和Y的一个最长公共子序列。 （1）如果xm=yn，那么zk=xm=yn，且Zk−1是Xm−1和Yn−1的一个最长公共子序列。 （2）如果xm≠yn，那么zk≠xm，蕴含着Z是Xm−1和Y的一个最长公共子序列。 （3）如果xm≠yn，那么zk≠yn，蕴含着Z是X和Yn−1的一个最长公共子序列。 2） 递归定义最优解的值 或且且l={0,i=0或j=0l,i,j>0且xi=yjmax(l,l),i,j>0且xi≠yj 3） 代码演示 C++ ​x941#include <algorithm> 2 #include <iostream> 3 #include <vector> 4 5 using std::cout; 6 using std::endl; 7 using std::string; 8 using std::vector; 9 10 11 12 //算法主体 13 void Match(string x,string y,int lenx,int leny){ 14 15    //建立图表 16    vector<vector<std::pair<int,int>>> diagram(lenx+1); 17    for(auto & v:diagram){ 18        v.resize(leny+1,{0,0}); // 初始化 19   } 20     21 22    // pair的第二位用于表示当前字符是否属于X和Y的公共子序列 23    // 1，2分别表示“当前X的字符不在公共子序列中，且当前X_i与Y_j的LCS和X_(i-1)与Y_j的LCS一样\", 24    // ”当前Y的字符不在公共子序列中，且当前X_i与Y_j的LCS和X_i与Y_(j-1)的LCS一样\" 25    // 3表示当前X与Y字符相等，且X_i与Y_j的LCS等于X_(i-1)与Y_(j-1)的LCS+1 26    for(int i = 1; i < lenx+1 ; ++i){ 27        for(int j = 1; j < leny+1 ; ++j){ 28            if(x == y){ 29                diagram.first = diagram.first+1; 30                diagram.second = 3; 31           } 32            else{ 33                if(diagram.first > diagram.first){ 34                    diagram.first = diagram.first; 35