LeetCode 96 Unique Binary Search Trees

1954 단어

LeetCode 96 Unique Binary Search Trees


Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,Given n = 3, there are a total of 5 unique BST's.
다시 한 번 지능이 눌린 것 같아...첫 번째 느낌은 규칙을 찾아서 dp 방향으로 기대야 한다는 것이다...그러나 어떤 규칙도 알아내지 못했다...

BST의 중요한 특징 중 하나를 꼭 명심하세요!!!


BST를 중순으로 옮겨다니며 실제로 얻은 것은sorted array!!!


OK, 그럼 이 특성을 어떻게 활용해서 풀 수 있을까?
하나, 둘, 셋을 포함해서...n 이 n 개수의 모든 BST는 루트가 1 또는 루트가 2 또는...root는 n이고 n가지 상황입니다.
다음과 같이 나타낼 수 있습니다.
  • G(n): the number of unique BST for a sequence of length n.
  • F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.
  • G(n) = F(1, n) + F(2, n) + ... + F(n, n).

    • 우리가 마지막으로 구해야 할 것은 G(n)이지만 G(n)를 구하기 위해서는 루트가 i일 때 유닛 BST가 얼마나 많은지, 즉 F(i, n)를 먼저 구해야 한다.
    다음은 관건적인 단계로 들어가서 F(i, n)의 구해를 분석해 봅시다. n=7, i=3을 가정하면 모든 unique BST에서 순서가 반복되면 [1,2,3,4,5,6,7]을 얻을 수 있습니다.3을 루트로 하는 모든 BST를 고려하면 모두 몇 가지 가능성이 있습니까?우리는 먼저 왼쪽 나무를 보고 이때 대응한다[1,2]. G(2)가 나무를 심는 형식이 있다.다시 오른쪽 나무를 보면 이때 [4,5,6,7]에 대응한다. 같은 점증 수열이기 때문에 나무의 다른 형식은 [1,2,3,4]와 사실상 같기 때문에 모두 G(4)가지 형식이 있다.
    좌우에 각각 G(2)와 G(4)종이 가능하다는 것을 알았으니 간단한 곱셈 원리로 알 수 있다. 루트=3에 대응하는 BST는 모두 G(2)*G(4)종이 가능하다!!!
    즉,
  • F(i, n) = G(i-1) * G(n-i) 1 <= i <= n

    • 더 나아가 G(n):
  • G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

    • 코드:
    public class Solution {
    public int numTrees(int n) {
        if (n <= 0) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i-1-j];
            }
        }
        return dp[n];
    }
}

    참조:
    https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i/2
    poj 1159dp 메모
    [ZJOI2010] 정렬 개수

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage