[BackTracking]118. Pascal's Tria

• 分类：BackTracking
• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)

118. Pascal's Triangle

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

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

Example:

Input: 5

Output:

[

 [1],

 [1,1],

 [1,2,1],

 [1,3,3,1],

 [1,4,6,4,1]

]

代码：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        
        res=[]
        
        if numRows==0:
            return res
        
        self.helper(numRows,res)
        return res
    
    def helper(self,numRows,res):
        
        if numRows==1:
            res.append([1])
            return [1]
        
        prev=self.helper(numRows-1,res)
        current=[1 for i in range(numRows)]
        for i in range(1,numRows-1):
            current[i]=prev[i-1]+prev[i]
        res.append(current)
        return current

讨论：

1.这道题确实是个简单题，用迭代或者递归都可以做出来！