[leetcode] different binary search trees (recursion - recursion + memory search optimization - dynamic programming)

#LeetCode A daily topic 【 Special topic of binary tree 】

• Different binary search trees
  https://leetcode-cn.com/problems/unique-binary-search-trees/
• analysis
  Binary search tree , The value of the root node is greater than that of the left node and less than that of the right node , And each of its subtrees is a binary search tree .
  So determine the root node i after , The value of the left subtree must be [1,i) Between , The value of the right subtree must be in (i,n] Between .
  That is, it can be divided into sub problems ： The root node value of the left subtree j stay [1,i) in , The value of its left subtree must be in [i,j), The value of its right subtree must be in (j,i）… And so on .
  It is a recursive problem , Keep looking for the number of left subtrees and right subtrees , The end result is Number of left subtrees * Number of right subtrees ;

1. Recursion end condition , Section start Greater than end;
2. Recursive return value ： The left subtree has many possibilities , Right subtree also has many possibilities , Record the possible number ;
3. The smallest problem , This level recursion should do ： Number of left subtrees * Number of right subtrees

• Code implementation

	public int numTrees(int n) {
    
        return numTrees(1, n);
    }

    private int numTrees(int start, int end) {
    
        if (start > end) {
    
            return 1;
        }
        int sum = 0;
        for (int i = start; i <= end; i++) {
    
            //  Number of left subtrees 
            int left = numTrees(start, i - 1);

            //  Number of right subtrees 
            int right = numTrees(i + 1, end);

            // i As root node , Put together the left and right subtrees , Possible quantity 
            sum += left * right;
        }
        return sum;
    }

Because there are a lot of repeated calculations in recursion , So when n=18 When ,LeetCode Display timeout

As if n=18 Calculation i=10 The left subtree needs to be calculated 1-9 The value of the interval , Calculate again i=11 When you need 1-10 The value of the interval contains 1-9, That is, there is a double calculation . Then we can use memory search to search 1-9 The value of the interval is recorded , The next time you recurse, make a judgment , If there is one in the memory, take it directly , If not, put it in your memory .

• Optimize —— recursive + Memory search method

	public int numTrees(int n) {
    
        int[][] memory = new int[n + 2][n + 2];
        return numTreesMemory(1, n, memory);
    }
    
    //  Use memory search to optimize 
    //  Such as calculation 10 The number of left and right subtrees , Zuozi tree is in 1-9 Combination between ; When calculating 11 When , Zuozi tree is in 1-10 Combination between , Must include 1-9 etc. , That is, there are a lot of repeated calculations .
    //  Use a two-dimensional array to store start、end Calculated results of , Before preparing the recursive call, determine whether it is stored in memory , If there is any, take , If not, put in 
    private int numTreesMemory(int start, int end, int[][] memory) {
    
        if (start > end) {
    
            //  return 1 No 0, Indicates that the subtree is null, It's also possible 
            return 1;
        }
        int sum = 0;
        for (int i = start; i <= end; i++) {
    
            //  Number of left subtrees 
            int left = memory[start][i - 1] > 0 ? memory[start][i - 1] : numTreesMemory(start, i - 1, memory);

            //  Number of right subtrees 
            int right = memory[i + 1][end] > 0 ? memory[i + 1][end] : numTreesMemory(i + 1, end, memory);

            // i As root node , Put together the left and right subtrees , Possible quantity 
            sum += left * right;
            memory[start][i - 1] = left;
            memory[i + 1][end] = right;
        }
        return sum;
    }

Memory optimization based on the original code ,LeetCode Time consuming ：0ms

• Dynamic programming
  After reading the comments and explanations , It is a typical dynamic programming problem ;

  The key of dynamic programming is to find the recurrence formula ：

  	dp(0)=1
  	dp(1)=dp(0)*dp(0)=1
  	dp(2)=dp(0)*dp(1)+dp(1)*dp(0)=2
  	dp(3)=dp(0)*dp(2)+dp(1)*dp(1)+dp(2)*dp(0)=5
  	...
  	dp(n)=dp(0)*dp(n-1)+dp(1)*dp(n-2)+...+dp(n-1)*dp(0)
  	 namely 
  		   n
  	dp(n)= ∑ dp(i-1)*dp(n-i)
  	      i=1
  

  dp(n) Express ： from 1-n Number , The number of binary search trees that can be composed
  In fact, the process of finding the recursive formula is also the logic embodied in the above recursive algorithm , from 1-n As root respectively , stay [1,i) Find the number of left subtrees （ Yes i-1 Nodes ）, stay (i,n] Find the number of right subtrees （ Yes n-i Nodes ）, Finally, the cumulative sum
  Concrete realization ：

  //  Use dynamic programming , The recursive formula ：dp(n)=  Sum up (i=1~n) dp(i-1)*dp(n-i)
  public int numTreesDP(int n) {
        
      //  initialization dp
      int[] dp = new int[n + 1];
      dp[0] = 1;
  
      //  According to the recurrence formula 
      for (int i = 1; i <= n; i++) {
        
          for (int j = 1; j <= i; j++) {
        
              //  Calculate the result of each step ,i =》 1~n
              dp[i] += dp[j - 1] * dp[i - j];
          }
      }
      return dp[n];
  }
  

  LeetCode Time consuming ：0ms
  

  • summary
    The problem is solved through the first recursion —— recursive + Memory search optimization —— Dynamic programming , The algorithmic idea goes forward layer by layer , The most important thing is how to analyze the problem , Think of using recursion , In optimizing recursion , Then find the recurrence formula and use dynamic programming .