Problema
Los números de Catalan 1, 1, 2, 5, 14, 42, … cuentan muchas cosas: las cadenas equilibradas de n pares de paréntesis, los árboles binarios con n nodos y las formas de dividir un polígono convexo en triángulos. Empiezan con C(0) = 1 y cumplen C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).
Implementa catalan_numbers(n).
Entrada
n: el índice del último número de Catalan que se incluye.
Salida
Devuelve la lista [C(0), C(1), …, C(n)], que tiene n + 1 valores. C(35) es el mayor que cabe en un entero de 64 bits con signo, así que cuidado con el desbordamiento en los pasos intermedios.
Restricciones
0 ≤ n ≤ 35
Ejemplos
Entrada:
n = 4
Salida esperada:
expected = [1, 1, 2, 5, 14]
Entrada:
long long n = 4;
Salida esperada:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Entrada:
long n = 4;
Salida esperada:
long[] expected = new long[] {1, 1, 2, 5, 14};
Explicación
C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, así que la lista es [1, 1, 2, 5, 14].
Entrada:
n = 0
Salida esperada:
expected = [1]
Entrada:
long long n = 0;
Salida esperada:
std::vector<long long> expected = {1};
Entrada:
long n = 0;
Salida esperada:
long[] expected = new long[] {1};
Explicación
Solo se pide C(0) = 1: [1].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Guarda los valores en una lista a medida que los calculas.
Pista 2
C(k + 1) es una suma sobre i de C(i) × C(k − i).
Pista 3
Cada producto de esa suma es como mucho el valor final, así que con estos límites el método de la suma nunca se desborda.
Complejidad esperada
tiempo O(n^2), espacio extra O(n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.