Geek asks and answers

Number of binary search trees with a given extension of the right hand

For this array of different (unique) integers, I want to know the number of BSTs in all permutations with the right largest leverage of length k. (If k = 3, root-> right-> right is the leaf node)

(According to my current requirement, I cannot afford an algorithm with a cost greater than N ^ 3)

Two identical BSTs generated from different permutations are considered different.

So far my approach is:

Assume the function:

F(arr) = {a1, a2, a3...}

where a1 is the number of arrays with k = 1, a2 is the number of arrays with k2, etc.

F (arr [1: n]) = for i in the range from 1 to n (1 + df * F (subar, where each element is greater than arr [i])) Where df is the dynamic factor (n-1) C (the number of elements is less than arr [i])

I am trying to create dp to solve the problem

  • Array Sort
  • dp [i] [i] = 1
  • (j i-1 1) dp [j] [i] = dp [j] [i-1],

ex: arr {4, 3, 2, 1}, dp

          arr[i]  4   3   2   1
                +---+---+---+---+
         k = 1  | 1 | 1 | 2 | 6 |
                +---+---+---+---+
         k = 2  | - | 1 | 3 |11 |
                +---+---+---+---+
         k = 3  | - | - | 1 | 6 |
                +---+---+---+---+
         k = 4  | - | - | - | 1 |
                +---+---+---+---+
verification(n!) 1    2   6   24

, , , , .

.

edit: , 3D- dp. . edit: col 3 dp

+3
2

, , , . ( ) . , , , , i, , i, , i. ,

 6 8 3 5 4 2 7 1 9
 _   _     _   _


          6
    3           8
 2     5      7   9
1     4

( ...). , .. A008275 .

, . S(n,k) - n k . :

  • S(n, 0) = 0 n
  • S(n+1, k) = n*S(n, k) + S(n, k-1) n>0 k>0
0

.

  • . , , .

  • , N - k, N - , k - . , , (root (node1 (node2... nodeK)))

N:

public int numTrees(int n) {

    int[] ut = new int[Math.max(n + 1, 3)];

    ut[1] = 1;
    ut[2] = 2;

    for (int i = 3; i <= n; i++) {
        int u = 0;
        for (int j = 0; j < i; j++) {
            u += Math.max(1, ut[j]) * Math.max(1, ut[i - j - 1]);
        }
        ut[i] = u;
    }

    return ut[n];
}

O (n ^ 2) O (n) .

0

More articles:


All Articles