Menu

Subscribe

[JAVA/LeetCode] Top 100 Liked Question: 96. Unique Binary Search Trees

HEESOO on Leetcode

👀 문제

https://leetcode.com/problems/unique-binary-search-trees/submissions/

👊 도전

1. 설계

  1. DP를 이용한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 *
 * @author HEESOO
 *
 */
class Solution {
    
    public int numTrees(int n) {
        if(n<3) return n;
        
        int[] dp=new int[n+1];
        dp[0]=dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            for(int j=0;j<i;j++){
                dp[i]+=dp[j]*dp[i-1-j];
            }
        }
        
        return dp[n];
    }
    
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. DP를 이용한다
    • n=1이면 1 (dp[1]=1)
    • n=2이면 1(root)- 2(right) 또는 1(left)-2(root) 이므로 dp[2]=2
    • n=3인 경우, root가 1이면 left에는 아무것도 오지 않고, right는 {2,3}이 온다. {2,3}이나 {1,2}나 BST를 만드는 경우의 수는 같으므로 경우의 수는 1(left 경우의 수, dp[0])*dp2=2
    • root=2이면, left에는 {1}, right는 {3}이 온다. 따라서 경우의 수는 dp[1]*dp[1]=1
    • root=3이면 left에 {1,2}, right={null}이므로 dp[2]*dp[0]=2
    • 이를 모두 더하면 dp[3]=(dp[0]*dp[2])+(dp[1]*dp[1])+(dp[2]*dp[0])
    • 따라서 이를 점화식으로 나타내면 dp[x]=dp[0]*dp[x-1]+…+dp[x-1][0]이다.
    • 이를 for문을 통해 나타냈다. i가 x, j는 0부터 x-1까지 경우의 수를 모두 더하는데 사용한다.

👏 해결 완료!

멀고도 험난한 DP의 세계🤯