Contar formas de dividir un círculo usando N cuerdas que no se intersecan

Dado un número N, encuentre el número de formas en que puede dibujar N cuerdas en un círculo con 2*N puntos de modo que no se crucen 2 cuerdas. 
Dos modos son diferentes si existe un acorde que está presente de un modo y no del otro.
Ejemplos: 
 

Input : N = 2
Output : 2
Explanation: If points are numbered 1 to 4 in 
clockwise direction, then different ways to 
draw chords are:
{(1-2), (3-4)} and {(1-4), (2-3)}


Input : N = 1
Output : 1
Explanation: Draw a chord between points 1 and 2.

Si dibujamos una cuerda entre dos puntos cualesquiera, ¿puede observar que el conjunto actual de puntos se divide en dos conjuntos más pequeños S_1 y S_2? Si dibujamos una cuerda desde un punto en S_1 hasta un punto en S_2, seguramente cortará la cuerda que acabamos de dibujar. 
Entonces, podemos llegar a una recurrencia que Ways(n) = sum[i = 0 to n-1] { Ways(i)*Ways(ni-1) }. 
Aquí iteramos sobre i, asumiendo que el tamaño de uno de los conjuntos es i y el tamaño de otro conjunto automáticamente es (ni-1) dado que ya hemos usado un par de puntos y un par de puntos i en un conjunto. 
 

// cpp code to count ways
// to divide circle using
// N non-intersecting chords.
#include <bits/stdc++.h>
using namespace std;
 
int chordCnt( int A){
 
    // n = no of points required
    int n = 2 * A;
     
    // dp array containing the sum
    int dpArray[n + 1]={ 0 };
    dpArray[0] = 1;
    dpArray[2] = 1;
    for (int i=4;i<=n;i+=2){
        for (int j=0;j<i-1;j+=2){
             
          dpArray[i] +=
            (dpArray[j]*dpArray[i-2-j]);
        }
    }
 
    // returning the required number
    return dpArray[n];
}
// Driver function
int main()
{
 
    int N;
    N = 2;
cout<<chordCnt( N)<<'\n';
    N = 1;
cout<<chordCnt( N)<<'\n';
    N = 4;
cout<<chordCnt( N)<<'\n';
    return 0;
}
 
// This code is contributed by Gitanjali.

// Java code to count ways
// to divide circle using
// N non-intersecting chords.
import java.io.*;
 
class GFG {
    static int chordCnt(int A)
    {
 
        // n = no of points required
        int n = 2 * A;
 
        // dp array containing the sum
        int[] dpArray = new int[n + 1];
        dpArray[0] = 1;
        dpArray[2] = 1;
        for (int i = 4; i <= n; i += 2) {
            for (int j = 0; j < i - 1; j += 2)
            {
                dpArray[i] += (dpArray[j] *
                              dpArray[i - 2 - j]);
            }
        }
 
        // returning the required number
        return dpArray[n];
    }
    public static void main(String[] args)
    {
        int N;
        N = 2;
        System.out.println(chordCnt(N));
        N = 1;
        System.out.println(chordCnt(N));
        N = 4;
        System.out.println(chordCnt(N));
    }
}
 
// This code is contributed by Gitanjali.

# python code to count ways to divide
# circle using N non-intersecting chords.
def chordCnt( A):
 
    # n = no of points required
    n = 2 * A
 
    # dp array containing the sum
    dpArray = [0]*(n + 1)
    dpArray[0] = 1
    dpArray[2] = 1
    for i in range(4, n + 1, 2):
        for j in range(0, i-1, 2):
            dpArray[i] += (dpArray[j]*dpArray[i-2-j])
 
    # returning the required number
    return int(dpArray[n])
 
# driver code
N = 2
print(chordCnt( N))
N = 1
print(chordCnt( N))
N = 4
print(chordCnt( N))

// C# code to count ways to divide
// circle using N non-intersecting chords.
using System;
 
class GFG {
     
    static int chordCnt(int A)
    {
        // n = no of points required
        int n = 2 * A;
 
        // dp array containing the sum
        int[] dpArray = new int[n + 1];
        dpArray[0] = 1;
        dpArray[2] = 1;
         
        for (int i = 4; i <= n; i += 2)
        {
            for (int j = 0; j < i - 1; j += 2)
            {
                dpArray[i] += (dpArray[j] * dpArray[i - 2 - j]);
            }
        }
 
        // returning the required number
        return dpArray[n];
    }
     
    // Driver code
    public static void Main()
    {
        int N;
        N = 2;
        Console.WriteLine(chordCnt(N));
        N = 1;
        Console.WriteLine(chordCnt(N));
        N = 4;
        Console.WriteLine(chordCnt(N));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP code to count ways
// to divide circle using
// N non-intersecting chords.
function chordCnt( $A)
{
 
    // n = no of points required
    $n = 2 * $A;
     
    // dp array containing the sum
    $dpArray = array_fill(0, $n + 1, 0);
    $dpArray[0] = 1;
    $dpArray[2] = 1;
    for ($i = 4; $i <= $n; $i += 2)
    {
        for ($j = 0; $j < $i - 1; $j += 2)
        {
             
            $dpArray[$i] += ($dpArray[$j] *
                             $dpArray[$i - 2 - $j]);
        }
    }
 
    // returning the required number
    return $dpArray[$n];
}
 
// Driver Code
$N = 2;
echo chordCnt($N), "\n";
$N = 1;
echo chordCnt($N), "\n";
$N = 4;
echo chordCnt($N), "\n";
     
// This code is contributed by Ryuga
?>

<script>
 
// JavaScript code to count ways
// to divide circle using
// N non-intersecting chords.
 
function chordCnt( A){
 
    // n = no of points required
    var n = 2 * A;
     
    // dp array containing the sum
    var dpArray = Array(n+1).fill(0);
    dpArray[0] = 1;
    dpArray[2] = 1;
    for (var i=4;i<=n;i+=2){
        for (var j=0;j<i-1;j+=2){
             
          dpArray[i] +=
            (dpArray[j]*dpArray[i-2-j]);
        }
    }
 
    // returning the required number
    return dpArray[n];
}
 
 
// Driver function
var N;
N = 2;
document.write( chordCnt( N) + '<br>');
N = 1;
document.write( chordCnt( N) + '<br>');
N = 4;
document.write( chordCnt( N) + '<br>');
 
 
</script>

Producción:  

2
1
14

Complejidad de Tiempo: O(n ² ) 
Espacio Auxiliar: O(n)

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.