96. Different binary search trees (medium binary search tree dynamic planning)

96. Different binary search trees

Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ？ Returns the number of binary search trees satisfying the meaning of the question .

Example 1：

Input ：n = 3
Output ：5
Example 2：

Input ：n = 1
Output ：1

Tips ：

1 <= n <= 19

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/unique-binary-search-trees
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Use dynamic planning , Find the state transition equation .
set up g(n) Express n Number of different binary search trees with nodes , set up f(i,n) In order to i Root 、 The sequence length is n The number of different binary search trees , So there are g(n) = f(1, n) + f(2, n) + … + f(n, n). The boundary conditions g(0) = 1, g(1) = 1, about f(i,n), It should be based on i Is the product of different left subtrees and different right subtrees of the root node , namely f(i,n) = g(i - 1) * g(n - i), that g(n) = f(1, n) + f(2, n) + … + f(n, n) Medium f All can be used g Instead of .

Answer key （Java）

class Solution {
    
    public int numTrees(int n) {
    
        int[] g = new int[n + 1];
        g[0] = 1;
        g[1] = 1;
        for (int i = 2; i <= n; i++) {
    
            for (int j = 1; j <= i; j++) {
    
                g[i] += g[j - 1] * g[i - j];
            }
        }
        return g[n];
    }
}