118. Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Constraints : 1 <= numRows <= 30

As soon as i see this problem, pop up a idea...Recursive. Since we confront the idea of recursive from the very easy problem called 'Fibonnaci' problem, this another math people name problem is another good chance to remind the idea of recursive.

First attempt

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        n = numRows
 
        def inner(l: List) -> List[int]:
            inner_result = [1]
            l_length = len(l)
            for i in range(l_length-1):
                inner_result.append(l[i] + l[i+1])
            inner_result.append(1)
            return inner_result   

        if n == 1:
            return [[1]]
        elif n == 2:
            return [[1],[1,1]]
        else:
            result = self.generate(n-1)
            result.append(inner(result[-1]))
            return result

Let think about 3case. Assume that it is a function named as f. $f(3) = f(3-1) + [1, loop + of f(2), 1]$ something like this. The loop of plus in last past is inner function above. This Recurrence relation is the key of this recursive problem. Make it and drive it with code.. that's all.

Beat most of other solutions in time complexity.

How to solve recursive problem?

1. Make a recursion relation of problem.
2. Make module inside of the recursion to make code more readable.
3. Minimize the base cases.