BOJ 9251 LCS

質問する

2つの数の列を持つすべての部分の数の列の中で最も長い1つを検索します.

各文字列の長さ<=1000

に近づく

LCSは非常に有名で、典型的なアクセスなので、どのようにアクセスするかを議論するのではなく、問題を解決する方法に重点を置きます.

d[i][j]は、1つの文字列から1つの文字列へのサブ文字列と、もう1つの文字列からjへのサブ文字列へのLCSとして定義される.

dpで近づくと、最後に集中します.

iとjはLCSの最後の文字になります.
d[i-1][j-1]+1

iおよびjがLCSでない場合、

2-1. iを書かなければ
d[i-1][j]

2-2. jを書かなければ
d[i][j-1]

以上の3つの場合の最大値はd[i][j]である.

時間の複雑さ
総アレイ数*元素毎に参照する数=O(3 N 2)O(3 N^2)O(3 N 2)

LCSを解決する方法はLCSにのみ使用されますが、これは典型的なLCSであるため、覚えておくことをお勧めします.以下の画像は、文字列CALENDARおよびCABLENDRのLCSを表すDPを示す.基板値が0であることも明らかである.

コード#コード#

import java.io.*;
import java.util.*;

class baek__9251 {
    static String s;
    static String ss;
    static int[][] d = new int[1000][1000];

    static int go(int i, int j) {
        if (i < 0 || j < 0)
            return 0;

        if (d[i][j] != -1) {
            return d[i][j];
        }

        int a = go(i - 1, j - 1);
        if (s.charAt(i) == ss.charAt(j))
            a++;

        int b = go(i - 1, j);
        int c = go(i, j - 1);

        d[i][j] = Math.max(a, b);
        d[i][j] = Math.max(d[i][j], c);

        return d[i][j];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        s = br.readLine();
        ss = br.readLine();

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < ss.length(); j++) {
                d[i][j] = -1;
            }
        }

        System.out.print(go(s.length() - 1, ss.length() - 1));
    }
}