[leetcode 96] Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

1부터 n까지 사용하여 만들 수 있는 bst 경우의 수

 

Example:

Input: 3

Output: 5

Explanation: Given n = 3, there are a total of 5 unique BST's:

 

 

 

 

 

 

 

Constraints:

• 1 <= n <= 19

문제 풀이:

- dp 사용

- dp[i]는 i개의 노드를 사용하여 만들 수 있는 트리 경우의 수이다.

dp[0]은 노드가 하나도 없으면 만들 수 있는 트리의 수가 하나도 없는 한가지 경우 밖에 없으므로 1이다.

dp[1]은 1로만 트리를 만들 수 있으므로 역시 1

dp[2]는 2이다.

3부터 문제가 되기 시작하는데 이렇게 접근하면 된다.

1부터 3까지 각 숫자가 트리의 루트가 될 때 만들 수 있는 트리의 경우의 수를 체크하면 된다.

루트가 1일 경우 2와 3은 모두 1보다 크기 때문에 1의 왼쪽 서브트리는 없고, 오른쪽 서브트리는 노드 2개로 만들 수 있는 경우의 수다. 즉 왼쪽 서브 트리의 경우의 수는 dp[0] 오른쪽 트리의 경우의 수는 dp[2]가 된다.

루트가 2일 경우 왼쪽 오른쪽은 각각 1, 3으로 dp[1], dp[1]에 해당한다.

루트가 3일 경우 1의 경우와 반대이다. 

정리하자면

dp[i]는 dp[0] * dp[i-1] + dp[1] * dp[i-1] + .... + dp[i-1] * dp[0]이 된다.

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