727. Minimum Window Subsequence

동적 기획에서 가장 어려운 점은 DP 상태의 정의이다.그러나 DP의 사고 과정은 귀착에서 출발하는 것이 가장 좋다.만약에 S에 T를 포함하여subsequence의 최소 길이를 알고 싶다면 S의 각 점을 끝으로 하는 Tsubsequence를 포함하는 최소 길이를 알아야 한다.만약 S의 마지막 자모가 T의 마지막 자모와 같지 않다면 우리는 match n-1과 m;만약 S의 마지막 자모가 T의 마지막 자모와 같다면, 우리 match n-1과 m-1은
물론 DP의 정의는 여러 가지 정의 방식이 있을 수 있다.여기 DP 상태의 정의 dp[i][j]는 반드시 i자모로 끝나는 match 전 j자 문자의 최소 길이입니다.

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) { 
                dp[i][j] = -1; //     -1；
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                   if (dp[i - 1][j - 1] != -1) dp[i][j] = 1 + dp[i - 1][j - 1]; //     match    
                } else {
                    if (dp[ i - 1][j] != -1) dp[i][j] = 1 +  dp[i - 1][j];//     match    
                }
            }
        }

    public String minWindow(String S, String T) {
        int N = S.length(); int M = T.length();
        int[][] dp = new int[N + 1][M + 1];
        for (int j = 1; j <= M; j++) dp[0][j] = -1;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) { 
                dp[i][j] = -1;
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    if (dp[i - 1][j - 1] != -1) {
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    } 
                } else {
                    if (dp[ i - 1][j] != -1) dp[i][j] = 1 +  dp[i - 1][j];
                }
            }
        }
        int best = N + 1;
        String result = "";
        for (int right = M - 1; right <= N; right++) {
            if (dp[right][M] != -1 && dp[right][M]  < best) {
                best = dp[right][M];
                result = S.substring(right - best , right);
            }
        }
        return result;
    }
}