JAVA_LeetCode 96_Unique Binary Search Trees 풀이 class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; // 0개 노드로 만들 수 있는 트리는 1개 (null) dp[1] = 1; // 점화식 계산을 위해 dp[1]에 1로 초기화한다. // dp[i]는 총 i개의 노드로 만들 수 있는 BST 개수 for(int i = 2; i <= n; i++){ for(int j = 1; j <= i; j++){ // j를 루트로 선택 - 왼쪽 서브트리: j - 1개, 오른쪽 서브트리: i - j개 dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } } 이진검색트리, 이진검색트리 dp 적용, 점화식 계산(각 항 사이의 관계식) * 출처 https://leetcode.com/problems/unique-binary-search-t...
