【每日一题 春季16】1222. 密码脱落 & 1143. 最长公共子序列

发表于 Valine：
本文字数： 101 阅读时长 ≈ 1 分钟

Day16 AcWing 1222. 密码脱落
Day16 LeetCode 1143. 最长公共子序列

思路

  1. 动态规划分析
密码脱落

dp分析过程

f[L+1,R-1] 被覆盖掉

最长公共子序列
1
2
3
4
case1 text1不包含i, text2不包含j: f[i][j] = f[i-1][j-1]  //被覆盖掉
case2 text1包含i,   text2不包含j: f[i][j] = f[i-1][j] + 1  
case3 text1不包含i, text2包含j:   f[i][j] = f[i][j-1] + 1  
case4 text1包含i,   text2包含j:   f[i][j] = f[i-1][j-1] + 1

代码

1222. 密码脱落
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
30
31
32
33
//区间dp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
char s[N];
int f[N][N];

int main()
{
    scanf("%s", s);
    n = strlen(s);

    for (int len = 1; len <= n; len ++ )
        for (int i = 0; i + len - 1 < n; i ++ )
        {
            int j = i + len - 1;
            if (len == 1) f[i][j] = 1;
            else
            {
                f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                if (s[i] == s[j])
                    f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2);
            }
        }
    printf("%d\n", n - f[0][n - 1]);
    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
//特殊解法，反转字符串求最长公共子序列
#include<bits/stdc++.h>
using namespace std;

string a,b;

int main()
{
    cin>>a;
    int n=a.length();
    b=a;
    reverse(b.begin(),b.end());
    int f[n+1][n+1];
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i-1]==b[j-1])
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    cout<<n-f[n][n]<<endl;
    return 0;
}
1143. 最长公共子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size(),m=text2.size();
        int f[n+1][m+1];
        memset(f,0,sizeof(f));
        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]);
                if(text1[i-1]==text2[j-1])
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        return f[n][m];
    }
};