（ブログ記事からの転載）
[https://leetcode.com/problems/pascals-triangle/]
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
パスカルの三角形と言われるものを、数列を重ねていくことで作ります。
各々の数列は、上段の数列の2つの値の和になっているのが特徴です。
解答・解説
解法1
私のsubmitした手法です。
愚直にnumRows段目までの数列を1つ1つ作り、積み上げていきます。
上の段の数列の2つの値を足して新たな数列を計算するとき、
l_pre = [0]+ans[-1]+[0]
のように数列の両端に[0]を追加して、
l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)]
のようにすっきりしたループ処理となるようにしていします。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = []
if numRows > 0:
ans.append([1])
for _ in range(numRows-1):
l_pre = [0]+ans[-1]+[0]
l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)]
ans.append(l_nxt)
return ans
解法2
Discussionの中で、これは良いなと思った解法を紹介します。
pascal = [[1]*(i+1) for i in range(numRows)]
として、はじめに全ての値を1にしてnumRows段目までの三角形を作ってしまってから、正しい値を代入します。
解法1と比べて時間・空間計算量は変わりませんが、公式よりもさらにすっきりした美しい解法だと思います。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
pascal = [[1]*(i+1) for i in range(numRows)]
for i in range(numRows):
for j in range(1,i):
pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]
return pascal