[DP] LCS

Longest Common Subsequence(최장 공통 부분 문자열)

public int LCS(String str1, String str2) {
    int M=str1.length();
    int N=str2.length();
    int[][] dp=new int[M+1][N+1];
    for(int i=1; i<=M; i++){
      for(int j=1; j<=N;j++){
        if(str1.charAt(i-1)==str2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
        else dp[i][j]=Math.max(dp[i][j-1], dp[i-1][j]);
      }
    }
    return dp[M][N];
}

• 2차원 배열을 dp로 선언한다.(행은 문자열1의 길이+1, 열은 문자열2의 길이+1)
• 이중 for문으로 M과 N을 돈다.
• 점화식
  • if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1 (dp는 1부터 배정해야하기 때문에 str1, str2는 인덱스에 -1을 한다.)
  • else dp[i][j]=max(dp[i][j-1], dp[i-1][j]) (각 스트링의 문자를 하나 뺐을 때의 값 중 최대값을 넣는다.)