【39. 最长公共子序列】

思路

• 第一个字符串是a,第二个字符串是b。
• 划分依据（划分成四个子集）
  • 是以a[i]和b[j]是否包含在子序列当中
  • 一共四种情况a[i],a[j],a[i][j],都不选
  • 把f[i][j]所有的子序列全部都分到这四种情况
  • f[i][j]的最大值是我们这四个集合的最大值，再取max

注意

• 对于0 1 是序列不包含a[i],但是一定包含b[j],而f[i-1][j]是所有在第一个序列前i - 1个字母出现，且在第二个序列的前j个字母出现的子序列,所以f[i-1][j]包含0 1集合，所以可以用f[i-1][j]代替0 1 集合的最大值。
• 而且对于第一种集合f[i-1][j-1]可以不写，因为集合2（f[i-1][j]）与集合3（f[i][j-1]包含了集合1的情况

可以代替的原因

• 对于DP问题，属性有三种max, min, 数量
• 例子:
  • 求A,B,C的最大值，我们可以先求max(A,B),max(B,C),然后再求这俩个max的最大值。而这里B出现了俩次，所以对于求最大值和最小值的可以使用该方法，而求数量就不可以

总结：

题目

代码

#include 
#include 
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];     //字符串a和b
int f[N][N];

int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            
            //因为最后一个集合a[i]和b[i]，不一定存在，只有当序列a的第i个值与序列b的第j个值相等才可以
            //序列a是以i结尾，序列b是以j结尾，所以只有相等，才有可能是公共子序列
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
        
       
        
    }
     cout << f[n][m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

注意

'从下标为1的地方开始读取'
char a[N];    //这里不能换成string
int main()
{
   
   cin >> a + 1;

   for (int i = 0; i <= 5; i ++)
   {
        cout << a[i] << endl;
   }
    return 0;
}   
1
2
3
4
5
6
7
8
9
10
11
12
13

• 每个int四个字节（每个字母是一个字节）
• 所以a[1]是acbd这四个字母二进制表示，拼起来的整数长度