C++의 고유한 이진 검색 트리

정수 n이 있다고 가정하면 1에서 n까지의 값을 저장하는 구조적으로 고유한 모든 이진 검색 트리를 계산해야 합니다. 따라서 입력이 3이면 출력은 트리와 같이 5가 됩니다. -

C++의 고유한 이진 검색 트리

이 문제를 해결하기 위해 다음 단계를 따릅니다.

n + 1 크기의 배열 하나 만들기
dp[0] :=1
i:=1 ~ n
- j의 경우 :=0 ~ i – 1
  - dp[i] :=dp[i] + (dp[i – 1 – j] * dp[j])
반환 dp[n]

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numTrees(int n) {
      vector <int> dp(n+1);
      dp[0] = 1;
      for(int i =1;i<=n;i++){
         for(int j = 0;j<i;j++){
            //cout << j << " " << i-1-j << " " << j << endl;
            dp[i] += (dp[i-1-j] * dp[j]);
         }
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout << ob.numTrees(4);
}