中級 0件解決済み 正答率0%

Catalan Numbers

List the Catalan numbers C(0) to C(n).

このチャレンジで学べること

  • Build a sequence from earlier values
  • Use a sum of products recurrence
  • Avoid overflow in intermediate results

問題

翻訳を表示

The Catalan numbers 1, 1, 2, 5, 14, 42, … count many things: balanced strings of n pairs of parentheses, binary trees with n nodes, and ways to cut a convex polygon into triangles. They start with C(0) = 1 and satisfy C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).

Implement catalan_numbers(n).

Input

n: The index of the last Catalan number to include.

Output

Return the list [C(0), C(1), …, C(n)], which has n + 1 values. C(35) is the largest that fits in a signed 64-bit integer, so watch out for overflow in intermediate steps.

制約

0 ≤ n ≤ 35

例

例 1
入力:
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, so the list is [1, 1, 2, 5, 14].

例 2
入力:
n = 0

期待される出力:
expected = [1]
入力:
long long n = 0;

期待される出力:
std::vector<long long> expected = {1};
入力:
long n = 0;

期待される出力:
long[] expected = new long[] {1};

解説

Only C(0) = 1 is asked for: [1].

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

Store the values in a list as you compute them.

ヒント 2

C(k + 1) is a sum over i of C(i) × C(k − i).

ヒント 3

Each product in that sum is at most the final value, so the sum approach never overflows within the limits.

目安の計算量

O(n^2) time, O(n) extra space

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。