如果在制定编号时其值呈指数增长，如何 return 结果。基于节点数的有效 BST 排列

Question

问题陈述：给你一个整数 N。你必须确定编号为 1 到 N 的节点可以创建的有效 BST 的数量。例子：输入：- N = 5 arr[] = {1,2,3,4,100} 输出： 1个 2个 5个 14 25666077

我的代码如下：

CODE:
 
import java.io.*;
import java.util.*;
public class Main{
    public static int numOfTrees(int N){
        int[] t = new int[N+1];
        t[0] = 1;
        t[1] = 1;
        for(int lvl=2;lvl<=N;lvl++){
            for(int root=1;root<=lvl;root++){
                t[lvl] = t[lvl] + t[lvl-root]*t[root-1];
            }
        }
        return t[N];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int arr[] = new int[num];
        for(int i=0;i<num;i++){
            arr[i] = sc.nextInt();
        }
        for(int i=0;i<num;i++){
            System.out.println(numOfTrees(arr[i]));
        }
    }
}

现在，当我按照示例 I/P 在 arr[4] 中输入 100 时，函数 returns 是一个垃圾值。我尝试将其类型转换为 Long 对象类型，但没有任何区别。请通过编写整个程序来帮助我！

Answer 1

我用 BigDecimal 重写了你的逻辑。我希望你的计算是正确的。请指向文章，以便我仔细检查算法。

import java.math.BigInteger;
import java.util.*;

class Main {

    public static BigInteger numOfTrees(int N) {
        BigInteger[] t = new BigInteger[N + 1];
        for (int i = 0; i < t.length; i++) {
            t[i] = BigInteger.ZERO;
        }
        t[0] = BigInteger.ONE;
        t[1] = BigInteger.ONE;
        for (int lvl = 2; lvl <= N; lvl++) {
            for (int root = 1; root <= lvl; root++) {
                t[lvl] = t[lvl].add(
                        t[lvl - root].multiply(t[root - 1])
                );
            }
        }
        return t[N];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int arr[] = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < num; i++) {
            System.out.println(numOfTrees(arr[i]));
        }
    }
}

我输入了：

===========输出为================

1
2
5
14
896519947090131496687170070074100632420837521538745909320

如果在制定编号时其值呈指数增长，如何 return 结果。基于节点数的有效 BST 排列

How to return the result if its value becomes exponentially large while formulating the no. of valid BST Permutations on the basis of number of nodes

java

binary-search-tree

permutation

dsa