Dynamic Programing 2

유형 3) 값을 만들수 있는지 없는지, 개수 구하기

문제 1) 1학년
https://www.acmicpc.net/problem/5557

1. 복잡도 확인하기
- N * M <= 100 * 20 <= 2000

2. DP 문제유형
- 특정한 경우 경우의 개수 구하기

3. 부분문제 정의하기
- V[i] = 숫자들.
- Dp[i][j] = i번째 수까지 고려하고, j 수를 만드는 개수.
- 하양식
• 이전 DP 값.
○ i 번째 수를 더하는 경우, 이전 dp 
§ dp[i-1][j - v[i]]
○ I 번째 수를 빼는 경우 dp 값, 이전 dp
§ dp[i-1][j + v[i]]
• 연산
○ +=

4. DP 설계
D[0][v[0]] = 1;
    for (int i=1; i < N; i++) {
        for (int j=0; j <= 20; j++) {
            if (j-v[i] >= 0)  D[i][j] += D[i-1][j-v[i]];
            if (j+v[i] <= 20) D[i][j] += D[i-1][j+v[i]];
        }
    }
5. DP 테이블
- input
• 5
• 2 1 3 4 8 
- OUTPUT

유형 4) 문자열 DP
1. 가장 긴 증가하는 부분 수열 (LCS)
https://www.acmicpc.net/problem/9251

1. 복잡도 확인하기
- N = 1000 ( N * N = 1,000,000 ) <= 1억
2. DP 문제유형
- LCS
3. 부분문제 정의하기
- Dp[i][j] = 첫번째 문자열의 길이 i, 두번째 문자열의 길이 j 일때 최장 공통 부분 수열 길이
- 하양식
• 이전 dp 값.
○ 마지막 문자가 같은 경우 이전 dp 최대값
§ Dp[i-1][j-1]
○ 마지막 문자가 같지 않는 경우,
§ dp[i][j-1], dp[i-1][j]
• 연산
○ max

4. DP 설계
for (int i = 0; i <= 1001; i++) {
   dp[0][i] = 0;
  dp[i][0] = 0;
}
int x = strlen(A);
int y = strlen(B);
for (int i = 1; i <= x; i++) {
for (int j = 1; j <= y; j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
}
}
}
5. DP 테이블
- Input
• ACAY
• CAPC
- Output
• 0 0 0 0 0
• 0 0 1 1 1
• 0 1 1 1 2
• 0 1 2 2 2
• 0 1 2 2 2



유형 5) 구간합
3. 정사각형 문제
https://www.acmicpc.net/problem/1915

1. 복잡도 확인하기
- N * M = 1000 * 1000 == 천만 <= 1억
2. DP 문제유형
- 이전 이후 dp 값을 참조하여 값을 계산.
3. 부분문제 정의하기
- dp[i][j] = i, j 인덱스 일때, 최대 정사각형의 변의 길이
- 하양식
• 이전 사각형의 최대 변의 길이 
○ dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
• min
•

4. DP 설계
 for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            if (v[i][j] == '1') {
                d[i][j] = min(d[i-1][j], d[i][j-1]);
                d[i][j] = min(d[i-1][j-1], d[i][j]);
                d[i][j] += 1;
                ans = max(ans, d[i][j]);
            }
        }
    }
5. DP 테이블
- Input
• 4 4
• 0100
• 0111
• 1110
• 0010
- Output
• 0 1 0 0
• 0 1 1 1
• 1 1 2 0
• 0 0 1 0
• 4


4. 구간합 구하기 5
https://www.acmicpc.net/problem/11660

1. 복잡도 확인하기
- N * M = 1024 * 1024 = 1048576
2. DP 문제유형
- 이전 이후 dp 값을 참조하여 값을 계산.
3. 부분문제 정의하기
- S[i][j] = 표 i, j 인덱스의 값
- dp[i][j] = 0, 0 ~ i, j 인덱스 까지 구간합
- 하향식
• 이전 DP 값.
○ Dp[i-1][j-1], dp[i-1][j], dp[i][j - 1]
• 연산
○ + , -

4. DP 설계
- for (int i = 1; i <= N; i++) {
  for (int j = 1; j <= N; j++) {
     dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + S[i][j];
   }
}
5. DP 테이블
- Input
• 4 3
• 1 2 3 4
• 2 3 4 5
• 3 4 5 6
• 4 5 6 7
• 2 2 3 4
• 3 4 3 4
• 1 1 4 4
- Output
• 1 3 6 10
• 3 8 15 24
• 6 15 27 42
• 10 24 42 64