[アルゴリズム]Java/バックエンド/LCS/9251

9047 ワード
baekjoon DP Java テキストリンク
[アルゴリズム]Java/バックエンド/LCS/9251
質問する
質問リンク
方法
LCSアルゴリズムの式は次の通りです.

画像ソース
  • 文字列1および2は、それぞれ、長さ+1を行および列とする2次元配列
    • を作成する.
  • 0行と0列の値は0
    • です.
  • 第1列は、2文字列の文字
    • の比較を開始する.
  • 各文字が同じ場合、行-1と列-1の値を現在位置で1に加算します.
  • 各文字が異なる場合、現在値において、現在位置である前の行の値と前の列の値のうちの大きい値を
    • に入れる.
    4行目は、文字列1のn文字と文字列2のm文字が同じであれば、文字列1のn−1文字と文字列2のm−1文字との間の最長共通部分数列の長さに1を加算することを意味する.
    5行目の意味は、現在の文字列1のn文字と文字列2のm文字が異なるため、これまでで最も長い共通部分数列長の大きな値を現在の値に入れる
    コード#コード#
    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_9251_baekjoon {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str1 = " "+ br.readLine();
		String str2 = " "+ br.readLine();
		
		int row = str1.length();
		int col = str2.length();
		
		int[][] dp = new int[row][col];
		int len = 0;
		for(int i =1; i<row; i++) {
			for(int j=1; j<col; j++) {
				if(str1.charAt(i) == str2.charAt(j)) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}
				else {
					dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); 
				}
				
				len = Math.max(len, dp[i][j]);
			}
		}
		
		System.out.println(len);
		
	}

}
    JSON2OBJ
    flinkとsparkはScalaプログラミングのコードの対比を使います