Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3 Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0 Output: [1]
Example 3:
Input: rowIndex = 1 Output: [1,1]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
# def value(i, j, memory=None):
# if (i,j) in memory:
# return memory[(i,j)]
# if i == j or j == 0:
# return 1
# memory[(i,j)] = value(i-1, j-1, memory) + value(i-1, j, memory)
# return memory[(i,j)]
# memory = {}
# l = []
# for i in range(rowIndex+1):
# l.append(value(rowIndex, i, memory))
# return l
from functools import lru_cache
@lru_cache()
def value(i, j):
if i == j or j == 0:
return 1
return value(i-1, j-1) + value(i-1, j)
l = []
for i in range(rowIndex+1):
l.append(value(rowIndex, i))
return l