Pascal's Triangle
パスカルの三角形では、最初の行は [1] です。それ以降の各行は1つずつ要素が増え、1で始まり1で終わります。その間の各要素は、真上にある2つの要素の和です。整数 numRows が与えられます。三角形の最初の numRows 行を、最上段から順に、各行を整数の配列として返してください。
関数
- numRowsinteger
- 三角形を何行作るか
- 戻り値integer-2d-array
- 最初の numRows 行（上の行から順に）
制約
1 ≤ numRows ≤ 30- 最初の30行の各項目は、32ビット符号付き整数に収まります。最大値は77558760で、30行目の中央にあります。
例
- 入力
- numRows = 5
- 出力
- [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
- 説明
- 各内側の要素は、その上にある2つの要素を足したものです。4行目では、3 = 1 + 2、3 = 2 + 1 です。5行目では、4 = 1 + 3、6 = 3 + 3、4 = 3 + 1 です。
- 入力
- numRows = 1
- 出力
- [[1]]
- 説明
- 行が1つの場合、三角形は頂点の
[1]だけです。
提出時に隠しテスト+13件
発展問題
上の行を保持せず、1つの配列の最後の行だけを、行ごとにその場で更新しながら作れますか？内側のループはどちら向きに回す必要がありますか？その理由は何ですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
行 0 は
[1]で、行 1 は[1, 1]です。行rの長さはいくつで、最初と最後の要素は何ですか？各内側の要素に必要なのは、すぐ上の行にある2つの値だけです。行を順番に作成すれば、その行は必要になる前に必ず完成しています。
新しい各行はすべて1として開始します。次に、各内側の位置
cについて、前の行の位置c-1とcを足します。その行を追加して次に進みます。
解説
三角形を定義する規則は再帰的です。各要素は、その1つ上の行にある2つの要素の合計です。この規則を各要素について最初から評価すると、同じ値を何度も計算し直すことになり、行が1つ増えるごとに作業量は2倍になります。返すよう求められている各行は、そうした小さな問題の答えをそのまま保存したものなので、三角形を上から構築し、各行をその1つ前に構築した行から求めましょう。
すべてのエントリを再帰的に計算する
正しいが、最大のテストでは終わらない
考え方
行と行内の位置には0から番号を付けます。三角形の定義は関数になります。entry(row, col)は、colが0またはrowと等しい場合、つまり2つの辺では1で、それ以外の場合はentry(row-1, col-1) + entry(row-1, col)です。すべての行のすべての位置についてこの関数を呼び出せば、三角形ができます。これは定義そのものなので、完全に正しい方法です。
問題は呼び出し回数です。再帰は辺に達したときにだけ停止し、そこで1を返すため、値がvの要素を計算するには、およそ2v回の呼び出しが必要です。行rの合計は最大で2^rなので、30行を合わせるとおよそ2^31回、20億回を超える呼び出しが必要になります。同じ小さな要素が何百万回も再計算されます。entry(2, 1)は、その下にあるほぼすべての値の計算に含まれます。
アルゴリズム
entry(row, col)を記述します。colが 0 またはcolがrowと等しい場合は 1 を返します。- それ以外の場合は、
entry(row-1, col-1) + entry(row-1, col)を返します。 - 0 から
numRows-1までの各rowについて、0 からrowまでのすべてのcolに対するentry(row, col)を集めます。 - 行のリストを返します。
def pascalEntry(row, col):
if col == 0 or col == row:
return 1 # the edges of the triangle
return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)
def generate(numRows):
triangle = []
for row in range(numRows):
triangle.append([pascalEntry(row, col) for col in range(row + 1)])
return triangle各行をその上の行から作成します
考え方
再帰版は前の行の値を何度も求めますが、いずれにせよそれらの行を作っています。そこで、上から下へ順番に行を計算し、行 r を埋めるときには、すでに計算済みの行 r-1 から必要な値を直接読み取ります。すると、各要素の計算に必要なのは加算1回です。これが最も基本的な動的計画法です。小さな問題の答えを並べた表そのものが出力になります。
行 r は、両端を設定するために r + 1 個の1で初期化します。次に、位置1から r-1 までの各内側の位置 c について、値を above[c-1] + above[c] に設定します。行0と行1には内側の位置がないため、特別な場合分けをしなくても、それぞれ [1] と [1, 1] のままです。
三角形には 1 + 2 + ... + n 個、つまり約 n²/2 個の要素があり、各要素の計算には定数時間がかかるため、処理量は O(n²) です。いずれにせよ返す必要がある出力を除けば、このメソッドで追加のメモリは必要ありません。numRows = 30 の場合、20億回の呼び出しではなく、要素数は465個です。
アルゴリズム
- 空の行リストから始めます。
rowを 0 からnumRows-1まで順に処理し、row + 1個の 1 を作成します。colを 1 からrow-1まで順に処理し、その値を前の行の位置col-1とcolの合計に設定します。- 行を追加して続けます。リストを返します。
def generate(numRows):
triangle = [[1]]
for row in range(1, numRows):
above = triangle[-1]
values = [1] * (row + 1) # both edges are 1
for col in range(1, row):
values[col] = above[col - 1] + above[col]
triangle.append(values)
return triangle
落とし穴と境界ケース
ループは短いため、間違いは境界と最初の行に関するものです。
numRows + 1行を返してしまう。行番号を 0 から付ける場合、必要な最後の行はnumRows-1行目です。- 内側のループで端の位置まで処理してしまう。位置 0 には左側の親がなく、位置
rowには右側の親がないため、そこでabove[col-1]またはabove[col]を読み取ると範囲外になります。位置 1 からrow-1までだけを埋めてください。 - 行数が少ない場合に問題が起きる範囲指定を使う。Swift の
1..<rowはrowが 0 のときクラッシュし、R の2:(row-1)はrowが 2 のとき 1 までカウントダウンします。ガードを入れるか、内側の位置を 1 から始めることで、行 0 と 1 ではループが不要になるようにしてください。 - 階乗を使って要素を計算する。
C(29, 14)は int に収まりますが、29!は 64 ビット整数でもオーバーフローするため、階乗を使った式では下の行に誤った数値が表示されます。 - すべての行で同じ配列を再利用する。同じ配列を毎回追加してから変更すると、答えのすべての行が最後の行と同じになります。
よくある質問4
パスカルの三角形を生成する時間計算量はどれくらいですか？
1つ上の行から各行を作成するには、n 行の場合、O(n²) の時間がかかります。三角形には約 n²/2 個の要素があり、それぞれの計算に加算が1回必要だからです。出力の各要素を書き出す必要があるため、これは最適です。出力を除けば、追加の領域として O(1) を使用します。
パスカルの三角形は二項係数とどのように関係していますか？
0から数えたときの、行 r の k 番目の要素は二項係数 C(r, k) であり、r 個の項目から k 個を選ぶ方法の数です。各要素がその上にある2つの要素の和になるという規則は、恒等式 C(r, k) = C(r-1, k-1) + C(r-1, k) で表されます。これが、行 r の合計が 2^r になる理由でもあります。
その上の行を作らずに、1 行を計算できますか？
はい。1から始め、各次の項を直前の項から求めます：C(r, k) = C(r, k-1) × (r-k+1) / k。割り切れるように、割る前に掛け算を行い、積には64ビット整数を使います。すると、行 r は O(r) 時間で求められ、他の行は必要ありません。
パスカルの三角形が動的計画法の問題であるのはなぜですか？
各項目は2つのより小さな部分問題に依存し、その上にある項目も参照します。また、それらの部分問題は大きく重複しています。そのため、通常の再帰では同じ計算を何度もやり直します。行を順番に構築すれば、各部分問題を一度だけ保存して再利用できるため、指数時間の処理をO(n²)に抑えられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def generate(numRows):
# ここにコードを書いてくださいケース1
ケース2
入力
numRows = 5
期待値
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]