Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return 

1
2
3
4
5
6
7
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

思路

帕斯卡三角，也就是杨辉三角，有着许多重要的性质。

在本题中，简单地利用该行元素和前一行元素之间的关系，就可以通过迭代的方式求得结果。

在这两行当中

1
2
3
4
  [1, 2, 1],
   \ / \ /
    |   |
[1, 3 , 3 ,1],

最后一行除了最左边的1以外，中间两个元素分别可以通过1+2=3求得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import copy
class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        res = []
        row1 = [1]
        row2 = [1,1]
        if (numRows <= 0):
            return res
        elif (numRows == 1):
            res.append(row1)
        else:
            res.append(row1)
            res.append(row2)
            # 利用浅拷贝来防止list出现混乱
            # 其实也完全可以不用
            prev = copy.copy(row2)
            while(numRows > 2):
                row = [1]
                length = len(prev)
                for i in range(len(prev)-1):
                    row.append(prev[i] + prev[i+1])
                row.append(1)
                res.append(row)
                prev = copy.copy(row)
                numRows -= 1
        return res