만나본 DP 문제 풀이 유형

최근에

2022.10.30 - [알고리즘/문제풀이] - 백준 문제풀이할 목록

에 있는 문제를 풀고 있는데 중요도가 높다고 생각되는 dp 문제를 풀면서 만났던 유형들을 정리해보았다. 

(아직 많은 문제를 풀어본 것이 아니라서 모든 dp 문제 풀이 유형을 정리한건 아니다.)

 

1. 단순한 점화식 사용

dp[i] = dp[i - 1] + dp[i - 2]; 
dp[i] = dp[i - 1] + n * dp[i - 2];

 

[1로 만들기](https://www.acmicpc.net/problem/1463)

 

[2×n 타일링](https://www.acmicpc.net/problem/11726)

 

[2×n 타일링 2](https://www.acmicpc.net/problem/11727)

 

[1, 2, 3 더하기](https://www.acmicpc.net/problem/9095)

 

[이친수](https://www.acmicpc.net/problem/2193)

 

[1, 2, 3 더하기 3](https://www.acmicpc.net/problem/15988)

 

[동물원](https://www.acmicpc.net/problem/1309)

 

 

2. dp[i] 와 dp[i - ?] 를 비교하기

dp[i] = Math.max(dp[i], dp[i - j]); 

dp[i] = Math.min(dp[i], dp[i - j]);

dp[i] = Math.min(dp[i - 2], dp[i - 1]) + arr[i];

...

[카드 구매하기](https://www.acmicpc.net/problem/11052)

[카드 구매하기 2](https://www.acmicpc.net/problem/16194)

 

[가장 긴 증가하는 부분 수열](https://www.acmicpc.net/problem/11053)

 

[가장 긴 증가하는 부분 수열 4](https://www.acmicpc.net/problem/14002)

 

[연속합](https://www.acmicpc.net/problem/1912)

 

[제곱수의 합](https://www.acmicpc.net/problem/1699)

 

[합분해](https://www.acmicpc.net/problem/2225)

 

[스티커](https://www.acmicpc.net/problem/9465)

 

[가장 큰 증가 부분 수열](https://www.acmicpc.net/problem/11055)

 

[가장 긴 감소하는 부분 수열](https://www.acmicpc.net/problem/11722)

 

3. 2차원 배열 사용하기

dp[i][j] = dp[i - 1][0] + dp[i - 2][1];

dp[i][2] = Math.max(dp[i - 1][0] + dp[i - 2][1]) + arr[i][2];

[1, 2, 3 더하기 5](https://www.acmicpc.net/problem/15990)

 

[쉬운 계단 수](https://www.acmicpc.net/problem/10844)

 

[RGB거리](https://www.acmicpc.net/problem/1149)

 

[오르막 수](https://www.acmicpc.net/problem/11057)