Problema
Os números de Catalan 1, 1, 2, 5, 14, 42, … contam muitas coisas: sequências balanceadas de n pares de parênteses, árvores binárias com n nós e maneiras de dividir um polígono convexo em triângulos. Eles começam com C(0) = 1 e satisfazem C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).
Implemente catalan_numbers(n).
Entrada
n: o índice do último número de Catalan a incluir.
Saída
Retorne a lista [C(0), C(1), …, C(n)], que tem n + 1 valores. C(35) é o maior que cabe em um inteiro de 64 bits com sinal, então cuidado com overflow nos passos intermediários.
Restrições
0 ≤ n ≤ 35
Exemplos
Entrada:
n = 4
Saída esperada:
expected = [1, 1, 2, 5, 14]
Entrada:
long long n = 4;
Saída esperada:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Entrada:
long n = 4;
Saída esperada:
long[] expected = new long[] {1, 1, 2, 5, 14};
Explicação
C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, então a lista é [1, 1, 2, 5, 14].
Entrada:
n = 0
Saída esperada:
expected = [1]
Entrada:
long long n = 0;
Saída esperada:
std::vector<long long> expected = {1};
Entrada:
long n = 0;
Saída esperada:
long[] expected = new long[] {1};
Explicação
Só C(0) = 1 é pedido: [1].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Guarde os valores em uma lista à medida que os calcula.
Dica 2
C(k + 1) é uma soma, para cada i, de C(i) × C(k − i).
Dica 3
Cada produto dessa soma é no máximo o valor final, então, dentro dos limites, esse método nunca estoura.
Complexidade esperada
tempo O(n^2), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.