Числа Каталана 1, 1, 2, 5, 14, 42, … считают очень многое: правильные скобочные последовательности из n пар скобок, двоичные деревья с n вершинами, способы разрезать выпуклый многоугольник на треугольники. Последовательность начинается с C(0) = 1 и подчиняется соотношению C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).
Реализуйте catalan_numbers(n).
Входные данные
n: номер последнего числа Каталана, которое нужно включить.
Выходные данные
Верните список [C(0), C(1), …, C(n)] из n + 1 значений. C(35) - наибольшее из чисел Каталана, которое помещается в знаковое 64-битное целое, поэтому следите за переполнением в промежуточных вычислениях.
Ограничения
0 ≤ n ≤ 35
Примеры
Ввод:
n = 4
Ожидаемый вывод:
expected = [1, 1, 2, 5, 14]
Ввод:
long long n = 4;
Ожидаемый вывод:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Ввод:
long n = 4;
Ожидаемый вывод:
long[] expected = new long[] {1, 1, 2, 5, 14};
Пояснение
C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, поэтому список равен [1, 1, 2, 5, 14].
Ввод:
n = 0
Ожидаемый вывод:
expected = [1]
Ввод:
long long n = 0;
Ожидаемый вывод:
std::vector<long long> expected = {1};
Ввод:
long n = 0;
Ожидаемый вывод:
long[] expected = new long[] {1};
Пояснение
Нужно только C(0) = 1: [1].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Сохраняйте значения в список по мере вычисления.
Подсказка 2
C(k + 1) - это сумма по i произведений C(i) × C(k − i).
Подсказка 3
Каждое произведение в этой сумме не больше итогового значения, поэтому в пределах ограничений сумма никогда не переполняется.
Ожидаемая сложность
время O(n^2), доп. память O(n)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.