leetcode || 96、Unique Binary Search Trees

problem:
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.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Hide Tags
 
Tree Dynamic Programming
제목: 크기가 N인 중복 요소가 없는 그룹으로 검색 트리의 수량을 구성할 수 있도록 합니다
thinking:
(1) 수량을 구하고 DP를 사용한다
(2) 귀속을 시작하여 제출 시간 초과
(3) DP의 사고방식은 모든 하위 구조를 두루 훑어보고 하나의 수조로 중간 결과를 저장하여 구해 과정을 가속화하는 것이다.
code:
DP:
class Solution {
public:
    int numTrees(int n) {
        vector<int> num;
        num.push_back(1);
        for(int i=1; i<=n; i++){
            num.push_back(0);
            if(i<3)
                num[i]=i;
            else{
                for(int j=1; j<=i; j++)
                    num[i]+=num[j-1]*num[i-j];
            }
        }
        return num[n];
    }
};

좋은 웹페이지 즐겨찾기