DP : 最长公共子序列

文章目录

• 求解思路
• 代码实现

---

这篇博客是听完郭炜老师的课之后的总结

---

求解思路

现在假设求两个字符串s1, s2的最长公共子序列
s1长度为len1, s2长度为len2, 我们设MaxLen(i, j)表示:
s1左边 i 个字符形成的子串, 与s2左边 j 个字符形成的子串的最长公共子序列长度

i, j 从 0 开始

那么我们最终求解的是 MaxLen( len1, len2 )的值

1. 那么我们首先能得到的是MaxLen(x , 0) = 0 和 MaxLen(0, x) = 0
   很明显, 因为一个空串和任意长度的字符串都不存在公共子序列
   这也是边界条件

2. 然后我们挨个比较两个字符串s1 s2, 当:
   s1[i - 1] == s2[j - 1]的时候, MaxLen(i, j) = MaxLen(i-1, j-1) + 1
   因为当我们从头挨个比较两个字符串的时候, 如果有两个字符相等, 那么说明他们是当前公共子序列的最后一个字符, 那么长度也就是之前的公共子序列长度 + 1了

3. 还有就是当s1[i -1] != s2[j - 1]的时候
   MaxLen(i, j) = max( MaxLen(i - 1, j), MaxLen(i, j - 1) )
   也就是说如果当前比较的这两个字符不相等时, 当前最长公共子序列长度等于 s1 自字符串前i - 1个字符和字符串 s2 前 j 个字符的公共子序列长度以及字符串 s1 前 i 个字符和 s2 前 j - 1 个字符的公共子序列之间的较大值

   这个式子的证明过程可以看上面贴的视频, 老师讲得很清楚

我们以一个二维数组表示MaxLen

0	0	0	0	0	0	0
0
0			MaxLen[i-1][j-1]	MaxLen[i-1] [j]
0			MaxLen[i][j-1]	MaxLen[i][j]
0
0

前面也说了边界条件, 先初始化这些为 0
然后根据上面说的推导过程, 我们要得到MaxLen[i][j]的值, 如果s1[i - 1] == s2[j - 1]的话. 就用MaxLen[i-1][j-1] + 1得到其值, 否则取MaxLen[i][j-1]和 MaxLen[i-1] [j]的较大值, 最后返回 `MaxLen[len1][len2]的值, 就是两个字符串的最长公共子序列的值

代码实现

/*
求最长公共子序列
*/

#include <string>
#include <iostream>
using namespace std;


int findLongest(string s1, string s2) 
{
    int maxLen[1000][1000];
    int len1 = s1.size(), 
    len2 = s2.size();
    for (int i = 0; i < len2; i++)
    maxLen[0][i] = 0;
    for (int i = 0; i < len1; i++)
    maxLen[i][0] = 0;

    for (int i = 1; i <= len1; i++) 
    for (int j = 1; j <= len2; j++) 
    {
        if (s1[i-1] == s2[j-1])
            maxLen[i][j] = maxLen[i-1][j-1] + 1;
        else 
            maxLen[i][j] = max(maxLen[i][j - 1], 
                               maxLen[i - 1][j]);
    }
    return maxLen[len1][len2];
}

int main() 
{
    string s1, s2;
    while (cin >> s1    
               >> s2) 
    {
        cout << s1 << ' ' << s2 
             << " 的最长公共子序列长度为 = " 
             << findLongest(s1, s2) 
             << endl;
    }
    return 0;
}