[数据结构与算法]DP5 有多少个不同的二叉搜索树

描述

给定一个由节点值从 1 到 n 的 n 个节点。请问由多少种不同的方法用这 n 个节点构成互不相同的二叉搜索树。

数据范围：?1 \le n \le 19 \1≤n≤19?

输入描述：

仅一行输入一个正整数 n ，表示节点的数量。

输出描述：

输出组成不同二叉搜索树的方法数。

分析

二叉搜索树是 有序的，左 > 根 >右

输出结果 = sum(左 * 右)，且对于n个节点，必存在?左 +?右 =?节点数 -1

代码

#include <stdio.h>
#include <malloc.h>
#define MAX_SIZE 20
// 二叉搜索树是 有序的，左 > 根 >右
// 输出结果 = sum(左+ 右)
int fibilac(int n)
{
    int R[MAX_SIZE] = { 0 };
    R[0] = 1;
    R[1] = 1;
    //     R[2] = 2;
    //     R[3] = 5;
    int result = 0;
    if (1 >= n)
    {
        return R[n];
    }

    int tmp_1 = 0;
    int tmp_2 = n;
  
    for (int i = 0; i <= n; i++)
    {
        if (i < 2)
        {
            R[i] = 1;
            continue;
        }
        tmp_1 = 0;
        tmp_2 = i - 1;
        while (tmp_1 <= tmp_2)
        {
            R[i] += R[tmp_1++] * R[tmp_2--]*2;
        }
        if (0 == (i-1) % 2)
        {
            R[i] = R[i]  - R[(i - 1)/ 2] * R[(i - 1) / 2];
        }
    }



    return  R[n];
}

int main()
{
    int num = 0;
    scanf("%d", &num);

    printf("%d", fibilac(num));
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖