[DP] Leet code 118. Pascal's Triangle

 

leetcode.com/problems/pascals-triangle/

 

 

내가 푼 코드

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        
        result = [[1]]
        
        if numRows >= 2:
            result.append([1,1])
        
        if numRows >= 3:
            for k in range(3, numRows+1):
                temp = [1] * k
                for i in range(1, k-2+1):
                    temp[i] = result[k-2][i-1] + result[k-2][i]
                result.append(temp)
                             
                
        return result

 

솔루션 코드 (코드를 좀 더 일반화)

class Solution:
    def generate(self, num_rows):
        triangle = []

        for row_num in range(num_rows):
            # The first and last row elements are always 1.
            row = [None for _ in range(row_num+1)]
            row[0], row[-1] = 1, 1

            # Each triangle element is equal to the sum of the elements
            # above-and-to-the-left and above-and-to-the-right.
            for j in range(1, len(row)-1):
                row[j] = triangle[row_num-1][j-1] + triangle[row_num-1][j]

            triangle.append(row)

        return triangle

 

시간복잡도 : O(N^2)

공간복잡도 : O(N^2)