# Leetcode 118. Pascal's Triangle

## 題解

### DP

#### SOS

output[y][x] = output[y-1][x-1] + output[y-1][x]

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        output = [[1]]
        if numRows == 1:
            return output
        
        for y in range(1,numRows):
            ans = []
            for x in range(y+1):
                left = output[y-1][x-1] if x-1 >= 0 else 0
                right = output[y-1][x] if x < len(output[y-1]) else 0
                ans.append(left+right)
            output.append(ans)
        
        return output