N个节点二叉树的形状个数 C语言实现

// f(0) = 1

// f(1) = 1

// f(2) = f(1)*f(0) + f(0)*f(1) = 2

// f(3) = f(2)*f(0) + f(1)*f(1) + f(0)*f(2) = 2*1 + 1*1 + 1*2 = 5

// f(4) = f(3)*f(0) + f(2)*f(1) + f(1)*f(2) + f(0)*f(3) = 5*1 + 2*1 + 1*2 + 1*5 = 14


#include <stdio.h>

int f(int n)
{
    if (n == 0 || \
        n == 1)
    {
        return 1;
    }
    int sum = 0;
    int i = 0;
    for (i =0; i<n; i++)
    {
        sum += f(i)*f(n-i-1);
    }
    return sum;
}

int main()
{
    printf("%d\n", f(16));
    return 1;
}


// f(0) = 1

// f(1) = 1

// f(2) = f(1)*f(0) + f(0)*f(1) = 2

// f(3) = f(2)*f(0) + f(1)*f(1) + f(0)*f(2) = 2*1 + 1*1 + 1*2 = 5

// f(4) = f(3)*f(0) + f(2)*f(1) + f(1)*f(2) + f(0)*f(3) = 5*1 + 2*1 + 1*2 + 1*5 = 14


#include <stdio.h>

int f(int n, int a[])
{
    if (a[n])
    {
        return a[n];
    }
    int sum = 0;
    int i = 0;
    for (i =0; i<n; i++)
    {
        sum += f(i, a)*f(n-i-1, a);
    }
    a[n] = sum;
    return sum;
}

int a[100];

int main()
{
    a[0]=1;
    a[1]=1;
    printf("%d\n", f(16, a));
    return 1;
}