max heap hint

• 접근 방법 : dynamic programming
• 시간 복잡도 : O(n^2)

dy[n] : 노드 수 n 으로 만들수 있는 max-heap 의 수로 정의.그러면 dy[1] = 1

n 이 5 인 경우 heap 은 그림과 같은 형태

왼쪽 서브트리의 수가 3 개 , 오른쪽 서브 트리의 수가 1

dy[5] = dy[3] * dy[1] * 4C3

4C3 인 이유는 왼쪽 서브트리에 올 수 있는 노드는 4 가지

• 1 , 2 , 3
• 1 , 2 , 4
• 1 , 3 , 4
• 2 , 3 , 4

일반화 하면

• 노드수가 n 일 때 왼쪽 서브트리의 수를 L , 오른쪽 서브트리의 수를 R 이라 하면

  • dy[n] = dy[L] * dy[R] * n-1 C L 혹은
  • dy[n] = dy[L] * dy[R] * n-1 C R