트리(Tree) & 트리 DP

📌 트리 DP

💬
DP(Dynamic Programming)? 부분 문제의 해를 이용하여 큰 문제의 해를 구한다. (DP는 보통 선형으로 이루어진 공간)

트리 DP란?

트리에서 dp를 하는 것. (트리는 비선형 구조)
서브 트리에서 구한 해를 이용하여 전체 트리의 해를 구한다.

어떤 로직으로 수행되나?

dp[i] = i를 루트로 하는 서브 트리의 ~~와 같은 식으로 dp 테이블을 정의한다.
트리에서 dp를 하기 전에 일반적으로 탐색 순서를 미리 정해준다.
탐색 순서는 dfs를 돌면서 나오는 트리, 즉 dfs tree를 기준으로 한다.
트리 dp도 대부분 상태 dp가 들어간다.
💬
상태 DP? ex) dp[i][j] = i를 루트로 하는 서브트리에서 i의 상태가 j일 때 ~~와 같은 식으로 한다.

📌 참고 자료

TOP