Leetcode-cn.com/problems/un…

The title

Given an integer n, how many binary search trees are composed of exactly n nodes with different values from 1 to n? Returns the number of binary search tree species that satisfy the problem.

Binary search tree BST is characterized by a node whose value is greater than or equal to all of its left subtrees and less than or equal to all of its right subtrees.

Train of thought

Exhaustive, dynamic programming

Four elements: base case, state (variables, i.e. total number of binary trees), selection (root node selection is different), BP function (implementation function is to return the number of binary trees)

How to achieve the BP function: first find the state transition equation.

The integers n, if 1… If n is the root node, the total number of BFS is:

G(n)=f(1)+f(2)+…. +f(n)

So how do I figure out the number of subtrees f of n that are root nodes

F (1), there’s only one way, there’s no number on the left, the number on the right has to be in order of magnitude;

F of 2, there’s only one way, one on the left, one on the right;

F (3), two kinds…

Seems to want to wrong, f (1) is not a, and should be G (0) * G (n – 1), the f (1) (2) is G * G (n – 2)…

Put it all together:

G(n)=G(0)*G(n-1)+G(1)*G(N-2)+… +G(i-1)*G(n-i)+… +G(n-1)*G(0);

The state transition equation is found and now the brute force solution is ready.

Violent solution

Public int numTrees(int n) {public int numTrees(int n) {[] dp =new int[n+1]; // base case dp[0]=1; dp[1]=1; // State transition equation: G(n)=G(0)*G(n-1)+G(1)*G(n-2)+... +G(i-1)*G(n-i)+... +G(n-1)*G(0); For (int I = 2; for (int I = 2; i <=n; I++){for (int j = 1; j<=i; J ++){// State transition equation dp[I] += dp[j-1]*dp[i-j]; } } return dp[n]; }}Copy the code

Debug

public int numTrees(int n) { // if(n==0){return 0; } // if(n==1){return 1; } int[] dp =new int[n]; dp[0]=0; dp[1]=1; for (int i = 2; i <=n; i++){ for (int j = 1; j<=i; j++ ){ dp[i]=dp[j-1]*dp[i-j]; } } return dp[n]; }}Copy the code

Analysis:int[] dp =new int[n];The array starts at 0, so it’s at most n minus 1, so for is out of bounds. Instead ofint[] dp =new int[n+1];

Analysis: With 3 beltdp[i]=dp[j-1]*dp[i-j];So this step is going to end up in dp[0],dp[n] is going to be a sum, in each case.

Dp [0]=0dp[2]=dp[0]dp[1]+dp[1]dp[0]=0Dp [0] should be set to 1: an empty binary tree is also a search binary tree

Recursively using memo optimization

private static Map<Integer, Integer> cache = new HashMap<>(); private int dfs(int n) { if (n <= 1) return 1; else if (cache.containsKey(n)) return cache.get(n); else { int c = 0; for (int i = 0; i < n; ++i) c += dfs(i) * dfs(n - i - 1); cache.put(n, c); return c; } } public int numTrees(int n) { return dfs(n); }}Copy the code

Author: Meteordream Link: leetcode-cn.com/problems/un…