forked from CodingVault/LeetCodeInPython
-
Notifications
You must be signed in to change notification settings - Fork 0
/
pascals_triangle.py
68 lines (54 loc) · 1.46 KB
/
pascals_triangle.py
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#!/usr/bin/env python
# encoding: utf-8
"""
pascals_triangle.py
Created by Shengwei on 2014-07-03.
"""
# https://oj.leetcode.com/problems/pascals-triangle/
# tags: easy / medium, triangle, dp
"""
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
"""
############ dp ############
def triangle(n):
if n == 1:
return [[1]]
sub_tria = triangle(n - 1)
last_line, new_line = sub_tria[-1], []
for i in range(len(last_line)):
if i == 0:
new_line.append(1)
continue
new_line.append(last_line[i] + last_line[i - 1])
new_line.append(1)
return sub_tria + [new_line]
############ V1 ############
class Solution:
# @return a list of lists of integers
def generate(self, numRows):
if numRows <= 0:
return []
res = [[1]]
if numRows == 1:
return res
for _ in xrange(1, numRows):
cur_level = []
upper_level = res[-1]
left = right = 0
for j in xrange(len(upper_level)):
left = right # for j == 0, left would be 0
right = upper_level[j]
cur_level.append(left + right)
# append the right most 1
cur_level.append(1)
res.append(cur_level)
return res