(DP, Medium) Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description/

힌트를 참고해서 2차원 배열로 dp배열을 만들면 된다는 아이디어를 보고..
text1과 text2의 길이를 이용한 dp배열을 만들었다.

이후 2중 for문으로 dp[i][j]값을 제어하면 되는데,
text1의 i-1 번째와 text2의 j-1번째가 같다면 서브시퀀스 한 칸 늘었다고 본다.
dp[i][j] = dp[i - 1][j - 1] + 1

그 외의 경우, 즉 서로 다른 글자로 출발해서 온 경우는
지금까지의 서브시퀀스 중 더 긴 쪽의 값을 세팅해야 하기 때문에 아래와 같이 한다.
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

그럼 max 서브시퀀스가 누계되어 새로 또 매치되는 글자를 찾을 때마다 max+1을 하게 되고
최종적으로 dp[text1.length()][text2.length()] 하게 되면 두 문자열의 가장 긴 공통 서브시퀀스를 찾을 수 있다.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {

        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for (int i=1; i<=text1.length(); i++) {
            for (int j=1; j<=text2.length(); j++) {
                
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}