LeetCode. Pascal's Triangle

Problem:

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

 

-Summary-

Solved by dynamic programming approach

(Below code is available from Leetcode solution)

1. The first and last element of each row is always 1.

2. Calculate inner elements by using and adding previous row elements.  

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

 

Time Complexity: O(numRows^2) --> double loop, the inner loop needs to be computed for each row.

Space Complexity: O(numRows^2) --> double array

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]