AcWing 897. 最长公共子序列

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 897. 最长公共子序列原题链接简单

作者：

小呆呆 , 2019-10-08 09:50:48 , 所有人可见 , 阅读 4420

13

6

算法分析

状态表示

集合：所有在A[1…i]中出现过且在B[1…j]中也出现过的子序列
属性：Max

状态计算（划分子集）

所有在 $A[1…i-1]$ 中出现过且在 $B[1…j]$ 中也出现过的子序列，最大长度 $为f[i -1][j]$
所有在 $A[1…i]$ 中出现过且在 $B[1…j-1]$ 中也出现过的子序列，最大长度为 $f[i][j - 1]$
当 $A[i] == B[j]$ 时,划分多一个子集所有在 $A[1…i-1]$ 中出现过且在 $B[1…j-1]$ 中也出现过的子序列，最大长度为 $f[i -1][j - 1] + 1$

时间复杂度 $O(n^2)$

Java 代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        String A = " " + scan.next();
        String B = " " + scan.next();
        int[][] f = new int[n + 1][m + 1];
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= m;j++)
            {

                f[i][j] = Math.max(f[i-1][j], f[i][j - 1]);
                //包含A[i] = B[j]情况的集合
                if(A.charAt(i) == B.charAt(j)) 
                    f[i][j] = Math.max(f[i][j],f[i - 1][j - 1] + 1);

            }
        }
        System.out.println(f[n][m]);

    }
}

6 评论

ACSaber 2021-04-11 21:51

为什么这样的做法不可行呢？

ACSaber 2021-04-11 21:51

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        String a = sc.next(), b = sc.next();
        a = " " + a;
        b = " " + b;
        char[] s1 = a.toCharArray(), s2 = b.toCharArray();
        int[][] f = new int[n + 1][m + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int max = Math.max(f[i - 1][j], f[i][j - 1]);
                if (s1[i] == s2[j]) {
                    max = Math.max(max, f[i - 1][j - 1] + 1);
                }
                f[i][j] = max;
            }
        }
        System.out.println(f[n][m] - 1);
    }
}

ACSaber 2021-04-11 21:50

你好有个疑问
我也是往 A 和 B 前面追加空格
并且令 f[0][0] = 1 代表空格部分被匹配了
最后输出答案的时候将 f[n][m] - 1 代表忽略第一个空格带来的影响
但是却无法 AC 是什么原因呢想了很久都不明白

晓月兮清风 2024-08-06 09:47

这里如果想“令 f[0][0] = 1 代表空格部分被匹配”，必须从0开始枚举i,j

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        String a = sc.next(), b = sc.next();
        a = " " + a + " ";
        b = " " + b + " ";
        char[] s1 = a.toCharArray(), s2 = b.toCharArray();
        int[][] f = new int[n + 2][m + 2];
        f[0][0] = 1;
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= m + 1; j++) {
                int max = Math.max(f[i > 0 ? i - 1 : n + 1][j], f[i][j > 0 ? j - 1 : m + 1]);
                if(a.charAt(i) == b.charAt(j)) 
                    max = Math.max(max, f[i > 0 ? i - 1 : n + 1][j > 0 ? j - 1 : m + 1] + 1);

                f[i][j] = max;
            }
        }
        System.out.println(f[n][m] - 1);
    }
}