問題タブ [catalan]

与えられた n について、有効な括弧の有効な組み合わせの数を見つけます。私は彼にカタロニア語の数の直接式を伝えました (以前にこの問題に遭遇したため)、彼は特に動的計画法を使用したこの問題の解決策を望んでおり、テストケースを使用した説明付きの実用的な解決策を望んでいました.I実用的なソリューションにたどり着くことができませんでした。

例えば：

n=1 有効なパー=0

n=2 有効なパー=1

今、私はこの問題を理解したいだけです

説明を 1 つ見つけましたが、理解できませんでした。理解を助けることができますか、以下のロジックの詳細な説明を提供してもらえますか (これは正しいようです)。

C(n) が 2 * n の括弧で有効な括弧の数を表す場合、偶数の括弧が必要です。

C(0)=1 and for any n>0

C(n)=C(0) * C(n-1)+C(1) * C(n-2)+...+C(n-1) * C(0)=sum(i=0,n-1,C(i) * C(n-1-i))

「(」で開始し、「)」で閉じ括弧がどこにあるかを確認する必要があるため、それらの間に 2 * i の括弧がある場合、そのようなケースの数は ですC(i) * C(n-1-i)。