【LeetCode】118. Pascal’s Triangle 解答・解説【Python】

この記事は約3分で読めます。

 

問題

原文

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

 

Example 1:

Input: numRows = 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1

Output: [[1]]

 

Constraints:

  • 1 <= numRows <= 30

 

内容

整数の変数numRowsが与えられます。パスカルの三角形を返してください。パスカルの三角形では各数字は直上の2つの要素の合計値になります。

 

※正しくない可能性があります。

方針

・動的計画法(DP)では、最終的な返り値(多次元リスト)を全て1で初期化した状態で作成し、

計算が必要な個所に対して計算を行っていく

・再帰的な処理では、numRowsの1つ小さい数字で関数を再度呼び出し、計算が必要な個所を更新する。

解答

解答1:

[1]rangeの終端をnumRows + 1としているのは番兵?(配列外参照を防ぐため?)

[2]二重ループは、1つ目のループが行、2つ目のループが各列の値を処理

→各行の更新箇所は1,2行目は0、3行目は1、4行目は2という具合で(行数-2)個となる。

for文のrangeで終端を示すときは(行数-1)個となる→for文のrangeの終端はループ実行回数に含まれないため。4行目の場合、for i in range(1,3):となり、4行目の(0から数えて)1,2番目の要素を処理する。

[3]ans[i][j]は更新箇所、ans[i-1][j]は更新箇所の右上、 ans[i-1][j-1]は更新箇所の左上の要素

解答2:動的計画法

 

numRowsの値が5なら、4→3→2→1という順で呼び出す。 ”if numRows”では、numRowsが0の時には実行されないので最初にnumRowsが1の時に

 

補足・参考・感想

参考

 

 

 

前:112. Path Sum

次:119. Pascal’s Triangle II

LeetCode 解答・解説記事一覧

コメント