动态规划

思想：

将待求解的问题分解成若干子问题，现求解子问题，然后从这些子问题得到问题的解，子问题之间不是独立的，并且将保存子问题的解

一般步骤

1.找出最优解的性质，并刻画其结构特征 2.递归定义最优值 3.以自底向上的方式计算出最优值 4.根据计算最优值时得到的信息，构造最优解 由此可以看出动态规划的两个重要性质:最优子结构(最优解包含其子问题最优解)和重叠子问题性质

动态规划----最长公共子序列

1.最长公共子序列的结构

设序列X={x1,x2,…,xm}和Y={y1,y2,…yn}的最长公共子序列为Z={z1,z2,…zk},则 (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.子问题的递归结构

用c[i] [j]记录序列Xi和Yj的最长公共子序列的长度，当i=0或j=0空序列是最长公共子序列，故此时c[i] [j]=0,在其他情况下，由最优子结构性质可建立递归关系如下:

0 i=0,j=0 c[i][j] = c[i-1][j-1]+1 i,j>0;xi=yj max{c[i][j-1],c[i-1][j]} i,j>0;xi!=yj

注意：

最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么，{a, 1, 1}是X和Y的最长公共子序列，但不是它们的最长公共字串

3.计算最优值

vector<vector<int>> lcslength(string x, string y) { //下标和 vector<vector<int>> v; vector<vector<int>> b; v.resize(x.size() + 1); b.resize(x.size() + 1); for (size_t i = 0; i < x.size()+1; i++) { v[i].resize(y.size() + 1); b[i].resize(y.size() + 1); } int size1 = x.size() + 1; int size2 = y.size() + 1; // v[i][j] 理解清楚i 和j 的意义 for (size_t i = 0; i < size1; i++) { v[i][0] = 0; b[i][0] = 0; } for (size_t i = 0; i < size2; i++) { v[0][i] = 0; b[0][i] = 0; } for (size_t i = 1; i < size1; i++) { for (size_t j = 1; j < size2; j++) { // i-1 == j-1 从下到上 从无到有的一个推导过程 if (x[i-1] == y[j-1]) { v[i][j] = v[i - 1][j - 1] + 1; b[i][j] = 1; } else if (v[i - 1][j] >= v[i][j - 1]) { v[i][j] = v[i - 1][j]; b[i][j] = 2; } else { v[i][j] = v[i][j - 1]; b[i][j] = 3; } } } return v; } //构造最长公告子序列 void calc(int i, int j, const string& x,const vector<vector<int>>& b) { if (i == 0 || j == 0) { return; } if (b[i][j] == 1) { calc(i - 1, j - 1, x, b); cout << x[i - 1]; } else if (b[i][j] == 2) calc(i - 1, j, x, b); else calc(i, j - 1, x, b); } //构造所有最长公共子序列 vector<string> g; void all(int i, int j,string x,string y,vector<vector<int>> v,string lcs) { //if (i == 0 || j == 0) // return; while (i>0&&j>0) { if (x[i-1] == y[j-1]) { lcs = x[i-1] + lcs; i--; j--; } else if (v[i - 1][j] == v[i][j - 1]) { //相当说明最长公共序列有多个 故两边都要回溯 all(i - 1, j, x, y, v, lcs); all(i, j - 1, x, y, v, lcs); return; } else if (v[i - 1][j] > v[i][j - 1]) { i--; } else { j--; } } g.push_back(lcs); } int main() { string x("ABCBDAB"); string y("BDCABA"); vector<vector<int>> out = lcslength(x, y); string lcs; all(x.size(), y.size(), x,y, out,lcs); int i = 1; system("pause"); return 0; }