动态规划
思想:
将待求解的问题分解成若干子问题,现求解子问题,然后从这些子问题得到问题的解,子问题之间不是独立的,并且将保存子问题的解
一般步骤
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;
}