[코드트리] 서로 다른 BST 개수 세기

문제링크

문제

n 이 주어지면 n개의 노드로 만들 수 있는 BST 개수 출력

문제 풀이

• dp로 문제를 푸는 것은 알겠음 -> 어떤 규칙이 있는지.
• 모든 경우의 총합을 구하기

// node가 4인 경우에
// root로 한개 있고
// 왼쪽에 0개 오른쪽에 3개
// 왼쪽에 1개 오른쪽에 2개 ... 의 모든 경우를 다 더하기
dp[4] = dp[0] * dp[3] + dp[1] * dp[2] + dp[2] * dp[1] + dp[3] * dp[0];

풀이 코드

import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        
        dp[0] = 1; // node가 0인 경우는 1가지 밖에 없음

        int sum = 0;
        for (int i = 1; i <= n; i++){
            sum = 0;
            for (int j = 0; j < i; j++)
                sum += dp[j] * dp[i - 1 - j];
            dp[i] = sum;
        }

        System.out.print(dp[n]);
    }
}