118. 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

풀이

단순하게 계속 연산해 나가면 된다. 만약 N번째 row의 파스칼 삼각형 row를 계산하라고 하고 메모리 제한을 빡빡하게 뒀으면 조금 더 방법을 고민해야했을수도...

직전 row의 값을 copy한 다음 앞에 0을 붙여 주면, prev[i] + prev[i+1] 값을 인덱스 고려 안하고 더해서 얻을 수 있다.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ret = [[1]]
        for i in range(1, numRows):
            bf_row = [0] + ret[i-1]
            curr_row = bf_row.copy()
            for j in range(len(bf_row)-1):
                curr_row[j] = bf_row[j] + bf_row[j+1]
            ret.append(curr_row)
        return ret