카테고리 E에서는 $7$가지 유형의 동적 계획법에 대해서 다룬다. 다루는 유형은 다음과 같다.
- 누적합(Prefix Sum)
- 최장 증가 부분수열(Longest Increasing Subsequence, LIS)
- 최장 공통 부분수열(Longest Common Subsequence, LCS)
- 비트필드를 이용한 동적 계획법(Bit DP)
- 트리에서의 동적 계획법(Tree DP)
- 덱을 이용한 동적 계획법(Deque DP)
- 부분집합의 합(Sum over Subsets, SOS DP)
SOS DP는 비트필드를 이용하기 때문에 Bit DP의 일종이지만 따로 분류했다. 이 $7$가지 유형의 동적 계획법을 응용하는 방법은 매우 많으므로 많은 문제를 접하면서 익숙해지는 것이 좋다.
'Algorithm > E. Dynamic Programming' 카테고리의 다른 글
| 80. Tree DP (0) | 2021.07.21 |
|---|---|
| 79. Bit DP (0) | 2021.07.13 |
| 78. Longest Common Subsequence (2) | 2021.07.07 |
| 77. Longest Increasing Subsequence (0) | 2021.07.02 |
| 76. Prefix Sum (1) | 2021.07.01 |
