[힘] DP(Dynamic Planning) 문제 분류 요약(二)

3. 구간DP
3.1 회문 서열
메시지 구간 DP 템플릿:

for (int i = 0; i < n; i ++) {
     
            dp[i][i] = true;
            res ++;
        }
        for (int i = n - 1; i >= 0; i --) {
     
            for (int j = i + 1; j < n; j ++) {
     
                //   s[i] == s[j],dp[i][j]  dp[i + 1][j - 1]
                //      
            }
        }

제목1: 회문자열(647. 회문자열)
문제풀이: 문자열의 DP는 일반적으로 2차원 그룹으로 구해야 한다.두 개의 바늘 dp[i][j]를 도입했는데 이 상태는 문자열 구간 dp[i+1][j-1]에서 옮겨온 것으로 그 결과 s[i]=s[j]가 성립되었는지 여부를 확정했다.코드는 다음과 같습니다.

class Solution {
     
    public int countSubstrings(String s) {
     
        if (null == s || 0 == s.length()) {
     
            return 0;
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        //     
        int res = 0;
        for (int i = 0; i < n; i ++) {
     
            dp[i][i] = true;
            res ++;
        }
        for (int i = n - 1; i >= 0; i --) {
     
            for (int j = i + 1; j < n; j ++) {
     
                // j - i == 1              true
                if (s.charAt(i) == s.charAt(j) && ((j - i == 1) || (dp[i + 1][j - 1]))) {
     
                    dp[i][j] = true;
                    res ++;
                }
            }
        }
        return res;
    }
}

제목2: 최장 회문 서열(516. 최장 회문 서열)
문제풀이:boolean의 dp 2차원 그룹을 만들고 dp[i][j]가 회문 문자열인지 판단합니다.최대 길이와 시작 위치를 기록합니다.

class Solution {
     
    public String longestPalindrome(String s) {
     
        if (null == s || 0 == s.length()) {
     
            return "";
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n ; i ++) {
     
            dp[i][i] = true;
        }
        int len = 0, maxLen = 1, index = 0;
        for (int i = n - 1; i >= 0; i --) {
     
            for (int j = i + 1; j < n ; j ++) {
     
                if(s.charAt(i) == s.charAt(j) && ((j - i == 1) || dp[i + 1][j - 1])) {
     
                    dp[i][j] = true;
                    len = j - i + 1;
                }
                //              
                if (dp[i][j] && len > maxLen) {
     
                    maxLen = len;
                    index = i;
                }
            }
        }
        return s.substring(index, index + maxLen);
    }
}

4. 게임형 DP
4.1 Nim 게임
제목1:292.Nim 게임(292. Nim 게임)
문제풀이: dpp[i]는 돌의 수량이 i일 때 자신의 승패 상황을 나타낸다.dp[i]의 결과는 dp[i-1], dp[i-2], dp[i-3]에false가 있는데 자신이 이번에 이길 수 있다.안 그러면 지는 거야.상태 전이 방정식: dp[i]=!dp[i - 1] || !dp[i - 2] || !dp[i - 3]; 코드는 다음과 같습니다.

class Solution {
     
    public boolean canWinNim(int n) {
     
    	//      
        // if (1 == n || 2 == n || 3 == n) {
     
        //     return true;
        // }
        // boolean[] dp = new boolean[n + 1];
        // dp[1] = true;
        // dp[2] = true;
        // dp[3] = true;
        // for (int i = 4; i <= n; i ++) {
     
        //     dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
        // }
        // return dp[n];

		//      
        // if (1 == n || 2 == n || 3 == n) {
     
        //     return true;
        // }
        // if (n % 4 != 0) {
     
        //     return true;
        // }
        // boolean dp_1 = true, dp_2 = true, dp_3 = true, dp = false;
        // for (int i = 4; i <= n; i ++) {
     
        //     dp = !dp_1 || !dp_2 || !dp_3;
        //     dp_1 = dp_2;
        //     dp_2 = dp_3;
        //     dp_3 = dp;
        // }
        // return dp;
        //      ：    
        return n % 4 != 0;
    }
}