amok   1년 전

dp(chosen, i, k): i번 노드를 루트로 하는 서브트리에서 총 k개의 노드를 선택했을 때의 간선 가중치의 합의 최솟값 (i번 노드는 chosen의 값에 따라 선택하던지, 선택하지 않던지 함)

으로 놓고 풀려고 시도했는데...

한 노드의 자식 노드가 여러 개일 경우 자식들의 dp값으로부터 부모의 dp값을 구하려면 계산을 너무 많이 해야되네요


어떻게 접근해야 하죠?

appa   1년 전

답 역추적이... 헠헠... 어렵다...

댓글을 작성하려면 로그인해야 합니다.