boj9251 LCS

15144 ワード
白駿 金貨 DP テキストリンク

リンク


9251号：LCS

質問する


最長共通部分数列(LCS)の問題は、2つの数列が与えられたときに、すべての部分数列の中で最も長い数列を検索することです.
例えば、ACAYKPとCAPCAKのLCSがACAKになります.

入力


1行目と2行目には2つの文字列があります.文字列は大文字のみで構成され、最大1000文字から構成されます.

しゅつりょく


1行目の入力は、指定された2文字列のLCS長を出力します.

私の答え

  • LCSアルゴリズムを実装する.
  • LCS 2 Dアレイを生成します.
  • 文字列長+1の値を水平に配置します.
  • の縦横値を比較し、LCSアレイに充填します.
  • 同じ値
  • L[i][j]=L[i-1][j-1]+1
  • 値が異なる
  • L[i][j]=Math.max(L[i-1][j],L[i][j-1])
  • コアコード
    int[][] dp = new int[target.length+1][result.length+1];
        int answer = 0;
        for (int i = 0; i < target.length; i++) {
            for (int j = 0; j < result.length; j++) {
                if(target[i].equals(result[j])){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                }
                if(answer<dp[i+1][j+1]) answer = dp[i+1][j+1];
            }
        }
  • 完全コード
    package Baekjoon.java.gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class boj9251 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] target = br.readLine().split("");
        String[] result = br.readLine().split("");
        int[][] dp = new int[target.length+1][result.length+1];
        int answer = 0;
        for (int i = 0; i < target.length; i++) {
            for (int j = 0; j < result.length; j++) {
                if(target[i].equals(result[j])){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                }
                if(answer<dp[i+1][j+1]) answer = dp[i+1][j+1];
            }
        }

        System.out.println(answer);

    }
}

    • 結果


    [白俊]1436号映画監督
    Day 045