C++LeetCode 구현(96.유일한 이 진 트 리)

[LeetCode]96.Unique Binary Search Trees 하나 밖 에 없 는 이 진 트 리
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
이 문 제 는 실제로... 카 탈 란 수 카 탈 란 Numbe 카 탈 란 수 에 익숙 하지 않 은 어린이 신발 은 정말 만 들 기 어 려 울 수도 있다.그런데 사실 나 도 오늘 알았어.왜 카 탈 란 수 는 피 보 나치 수 처럼 다 알 지 못 하 는 걸 까?내 가 너무 과문 한 건 가?!하지만 오늘 은 알 아 도 늦 지 않 고 새로운 것 을 계속 공부 하 는 것 이 야 말로 문 제 를 푸 는 의미 가 있 잖 아!자,쓸데없는 말 은 그만 하고 어서 제목 으로 돌아 가자.n=1 의 상황 을 살 펴 보면 유일한 이 진 트 리 만 형성 할 수 있 습 니 다.n 은 각각 1,2,3 의 상황 은 다음 과 같 습 니 다.
                    1                        n = 1
                2        1                   n = 2
/          \
1            2
1         3     3      2      1           n = 3
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
피 보 나치 수열 과 마찬가지 로 우 리 는 n=0 시 를 1 로 부 여 했 습 니 다.빈 나무 도 이 진 트 리 라 고 할 수 있 기 때문에 n=1 시의 경 우 는 왼쪽 나무 개 수 를 오른쪽 나무 에 곱 한 개수 로 볼 수 있 습 니 다.좌우 자 나 무 는 모두 빈 나무 이기 때문에 1 곱 하기 1 입 니까?1 입 니까?그러면 n=2 는 1 과 2 가 모두 뿌리 가 될 수 있 기 때문에 각각 계산 한 다음 에 그것들 을 합치 면 된다.n=2 의 경우 다음 식 으로 계산 할 수 있 습 니 다(여기 dp[i]는 i 개의 숫자 로 구 성 된 BST 의 개 수 를 표시 합 니 다).
dp[2] =  dp[0]*dp[1](1 이 뿌리 인 경우 왼쪽 트 리 는 반드시 존재 하지 않 고 오른쪽 트 리 는 하나의 숫자 가 있 을 수 있 습 니 다)
　　　　+ dp[1] * dp[0]　　  (2.뿌리 인 경우 왼쪽 나무 에 숫자 가 있 을 수 있 고 오른쪽 나 무 는 존재 하지 않 습 니 다)
같은 이치 로 n=3 의 계산 방법 을 쓸 수 있다.
dp[3] =  dp[0]*dp[2](1 이 뿌리 인 경우 왼쪽 트 리 는 반드시 존재 하지 않 고 오른쪽 트 리 는 두 개의 숫자 가 있 을 수 있 습 니 다)
　　　　+ dp[1] * dp[1]　　  (2.뿌리 인 경우 에는 좌우 자나무 에 각각 하나의 숫자 가 있 을 수 있다)
 　　　  + dp[2] * dp[0]　　  (3.뿌리 인 경우 왼쪽 트 리 는 두 개의 숫자 가 있 을 수 있 고 오른쪽 트 리 는 존재 하지 않 습 니 다)
우 리 는 상기 분석 에 근거 하여 코드 를 다음 과 같이 쓸 수 있다.
해법 1:

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
};

카 틀 란 수의 전달 식 은 그 통 항 공식,즉 C(2n,n)/(n+1)을 추론 할 수 있다.2n 개의 숫자 에서 n 개의 수 를 임 의 하 는 방법 을 n+1 로 나 누 는 것 을 의미한다.고등학교 의 배열 조합 지식 을 잊 지 않 았 다 면 아래 의 코드 를 쓰기 어렵 지 않 을 것 이다.곱 할 때 정수 가 넘 치지 않도록 결과 res 를 긴 정형 으로 정의 해 야 한다.코드 는 다음 과 같다.
해법 2:

class Solution {
public:
    int numTrees(int n) {
        long res = 1;
        for (int i = n + 1; i <= 2 * n; ++i) {
            res = res * i / (i - n);
        }
        return res / (n + 1);
    }
};

C++구현 LeetCode(96.하나 밖 에 없 는 이 진 트 리)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 하나 밖 에 없 는 이 진 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부탁드립니다!