Lv.4右かっこの個数

問題の説明

データ構造

Molecular

タイプ:整数

格納データ:分子変数

denominator

タイプ:整数

格納データ:分母としての変数

解法

原理は

3 xnタイル問題

に類似する.
一般式を推測するために,いくつかの初期項を求める.
f(1) = 1, f(2) = 2 , f(3) = 5, f(4) = 14...
f(1) = ( )
f(2) = ( ) ( ), ( ( ) )

()()は、f(1)に括弧のペアを追加することができる.

ただし(()はf(1)カッコの後ろに付ける方法では作成できません.

の横に追加するように、2対の括弧を完全に充填できない場合をg(2)と呼ぶ.

->f(3)=f(1)に2対+f(2)に1対+g(3)を充填します.
->f(4)=f(1)中充填3対+f(2)中充填2対+f(3)中充填1対+g(4)
...
以下に整理します.

f(3) = g(3) + f(1) * g(2) + f(2) * g(1) + g(3)
f(4) = g(4) + f(1) * g(3) + f(2) * g(2) + f(3) * g(1)
f(5) = g(5) + f(1) * g(4) + f(2) * g(3) + f(3) * g(2) + f(4) * g(1)
...
f(n) = g(n) + f(1) * g(n-1) + f(2) * g(n-2) + ... f(i) * g(n-i) + ... + f(n-1) * g(1) 

g(n)の法則性を探る.

g(1) = ( )
g(2) = ( ( ) )
g(3) = ( ( ( ) ) ), ( ( ) ( ) ),
g(4) = ( ( ) ( ( ) ) ), ( ( ) ( ) ( ) ), ( ( ( ) ) ( ) ), ( ( ( ( ) ) ) ), ( ( ( ) ( ) ) )
...
()内にはn-1対の括弧があります.
n-1対のかっこを作成すると、f(n-1)の数になります.
すなわち,g(n)=f(n−1)であるため,一般項は以下のように整理される.

f(n) = f(n-1) * f(1) + f(n-2) * f(2) + ... +  f(1) * f(n-1)

これは下図のように整理します.

コード実装(JavaScript)

function solution(n) {
	let Molecular = n + 1, denominator = n;
        
	for (let i = 1; i < n; i++) {
        Molecular *= n + 1 + i; 
        denominator *= n - i;
   }
	return Number(Molecular / denominator) / (n + 1);
}

ソース:プログラマ