DP 팁

 

일단은, 나는 DFS나 BFS를 먼저 떠올린다.

너무 클 거 같다면 

1. 문제를 막 풀고 그 결론이 DP 

2. 앞에서 부터 DP 

(2번의 경우에는 DP[I] = DP[I-1]+_ORIGINAL[I-2]~~ 식으로 할 때, 어디까지 DP의 영향이 닿고, 어디부터 닿지 않는지를 고려하자)

3. 뒤에서 부터 DP (굉장히 어렵다) 

 

이걸 사실 암기처럼 할게 아니고,

1번의 경우는 수학적인 식이 DP라는 말이고 EX) Y = X+1 , Z = 2Y , Z = 2X+2 이런 느낌

2번의 경우, 3번의 경우는 지금 현재의 값이 어디에서 왔는가. 를 고민하고

어디까지 이전 값이 영향을 끼쳐도 되는가, 어디부터 안되는가 고민하면 된다. 

 

또, 단순한 1차원 행렬이 아닐 수도. 
기본적으로 dp가 2차원 행렬에서 이전 값이 다음 값의 어디에 영향을 주는가. 를 고민하는 것이기 때문에. 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()) ;

        int [] Narr = new int [N+1];

        for (int i = 1 ; i<=N ; i++)
            {
                Narr[i] = Integer.parseInt(br.readLine());
            }

        int [] dp = new int [N+1];

        dp[1] = Narr[1];

        if (N>=2)
        {
            dp[2] = Narr[1]+Narr[2];
        }

        for (int i =3 ; i<=N ;i++)
            {
                dp [i] = Math.max(dp[i-1],Math.max(dp[i-2]+ Narr[i],dp[i-3]+Narr[i-1]+ Narr[i]));
            }

        int answer = 0 ;
        for (int i = 0 ; i<=N ; i++)
            {
                answer = Math.max(answer,dp[i]);
            }

        System.out.print(answer);
    }
}

위가 예시 코드이고 다시, 핵심은. 
1. dp는 이전 값 기억 프로그래밍이다.
2. dp로 구현할 것은 무엇인가 (위 코드에선 n번째 포도주를 만났을 때, 최대 값)
3. DP의 제약은 무엇인가 (위 코드에선 3개 연속먹을 수 없음으로, 2개전 최대값까지 먹고 지금 먹고, 3개전 최대값 까지 먹고, 전꺼 먹고, 지금 꺼 먹고)
4. DP시 주의할 것은, 해당 I를 꼭 선택해야 하는 가, 아닌가.


상태 2개를 유지하려고 한다면? -> 2차원 배열을 활용하자. 
LCS로 문자열 A,B를 구분해야 한다거나 할 때.