tree dp (1) 썸네일형 리스트형 80. Tree DP 트리에서의 동적 계획법(Tree DP)에 대해 다룬다. 트리에 대한 내용을 전혀 다루지 않은 상태에서 트리 DP를 다루는 건 순서가 뒤바뀐 느낌이지만 트리 DP가 트리와 DP 중 DP에 더 가깝기 때문에 여기서 다루었다. 트리에 대한 내용은 카테고리 H에서 다루며, 기본적인 내용은 이 글을 참고하면 된다. 일반적으로 트리 DP를 시작하는 정점은 트리의 루트이며 루트 없는 트리가 주어지는 경우 임의의 정점을 하나 선택하면 되는 경우가 많다. 또한 자식 노드들의 DP 정보를 바탕으로 부모 노드의 DP 정보를 갱신하는 방법과 부모 노드의 DP 정보를 바탕으로 자식 노드의 DP 정보를 갱신하는 방법으로 구분할 수 있다. 일반적으로 전자가 더 많이 사용되는 것 같다. [연습문제] BOJ 15681. 트리와 쿼리 .. 이전 1 다음
