118. Pascal's 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:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Source
Code
In [1]:
def pascal_triangle(numRows):
"""Dynamic Programming approach."""
# Base cases
if numRows == 0:
return []
if numRows == 1:
return [[1]]
result = [[1], [1, 1]]
for i in range(2, numRows):
result.append([1, i]) # start new row with 1, i
for j in range(2, i):
result[i].append(result[i-1][j-1] + result[i-1][j])
result[i].append(1) # end row with 1
return result
Check
In [2]:
pascal_triangle(5)
Out[2]:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
In [3]:
pascal_triangle(15)
Out[3]:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1], [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1], [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1], [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1], [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1]]
Follow up:
Solve it both recursively and iteratively.
Code
In [4]:
def pascal_triangle(numRows):
"""Recursive approach."""
# Base cases
if numRows == 0:
return []
if numRows == 1:
return [[1]]
prev = pascal_triangle(numRows-1)
row = [1]*numRows
for i in range(1, numRows-1):
row[i] = prev[-1][i-1]+prev[-1][i]
return prev + [row]
Check
In [5]:
pascal_triangle(5)
Out[5]:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
In [6]:
pascal_triangle(15)
Out[6]:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1], [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1], [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1], [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1], [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1]]