看雪Unicorn高级逆向与反混淆
不同的二叉搜索树
public class BinarySearchTree {
// f(n) n个节点二叉搜索树
// g(i) i为根节点，n个节点的二叉搜索树
// 左子树一定有 i - 1 个元素 => 左子树有 f(i-1) 种情况
// 右子树一定有 n - i 个元素 => 右子树有 f(n-i) 中情况
// f(n) = g(1) + g(2) + g(3) + ... + g(n-1) + g(n)
// = f(0) * f(n-1) + f(1) * f(n-2) + f(2) * f(n-3) + ... + f(n-2) * f(1) + f(n-1) * f(0)
// f(3) = g(1) + g(2) + g(3)
// g(1) 左子树一定有0个元素，右子树一定有2个元素
// g(2) 左子树一定有1个元素，右子树一定有1个元素
// g(3) 左子树一定有2个元素，右子树一定有0个元素
public static int recursion(int n) {
if (n == 0) {
return 1;
}
if (n == 1 || n == 2) {
return n;
}
int result = 0;
for (int i = 0; i < n; i++) {
result += recursion(i) * recursion(n - i - 1);
}
return result;
}
public static int loop(int n) {
int[] result = new int[n + 1];
result[0] = 1;
if (n >= 0) {
result[1] = 1;
}
if (n >= 1) {
result[2] = 2;
}
for (int i = 3; i <= n; i++) {
// 计算第i个位置上的结果，第i个位置上的结果由前i-1个结果生成
int sum = 0;
for (int j = 0; j < i; j++) {
sum += result[j] * result[i - j - 1];
}
result[i] = sum;
}
return result[n];
}
public static void main(String[] args) {
System.out.println(loop(3));
}}
