Leetcode skimming: dynamic programming 07 (different binary search trees)

96. Different binary search trees

Force button topic link

Given an integer n, Seeking for 1 … n How many binary search trees are there for nodes ？

Example :

Didn't do it , The solution of the research problem was finally worked out . The idea is simple .
At present dp[ i ] The value of is that each node of all nodes in this tree is made a head node , The product of left subtree and right subtree changes is the sum , For example j Is the root node , More than j Left subtree composed of small numbers , Yes j - 1 Number , That is to say dp[ j - 1 ] Combinations of , Than j Large number , altogether i - j individual , Then the number of the right subtree has i - j individual , common dp [ i - j ] Change . Multiply left and right , For the current j Is the total change of nodes , All the total change is that each number is the head node , Sum of changes .

package com.programmercarl.dynamic;

/** * @ClassName NumTrees * @Descriotion TODO * @Author nitaotao * @Date 2022/7/25 17:00 * @Version 1.0 * https://leetcode.cn/problems/unique-binary-search-trees/ * 96.  Different binary search trees  **/
public class NumTrees {
    
    public int numTrees(int n) {
    
        /** *  Binary search tree , Ascending  * n>=1 */
        if (n <= 2) {
    
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
    
            // n>=1
            for (int j = 1; j < i; j++) {
    
                //dp[i] Each possibility is to take one of the numbers as the head node , Variation of left subtree * Variation of right subtree 
                //  With  dp[j] Is the head node 
                // Zuo Zi Shu you j-1 individual   Right subtree has i-j individual 
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}