forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
paint-fence.py
42 lines (39 loc) · 941 Bytes
/
paint-fence.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
# Time: O(n)
# Space: O(1)
class Solution(object):
def numWays(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
if n == 0:
return 0
elif n == 1:
return k
ways = [0] * 3
ways[0] = k
ways[1] = (k - 1) * ways[0] + k
for i in xrange(2, n):
ways[i % 3] = (k - 1) * (ways[(i - 1) % 3] + ways[(i - 2) % 3])
return ways[(n - 1) % 3]
# Time: O(n)
# Space: O(n)
# DP solution.
class Solution2(object):
def numWays(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
if n == 0:
return 0
elif n == 1:
return k
ways = [0] * n
ways[0] = k
ways[1] = (k - 1) * ways[0] + k
for i in xrange(2, n):
ways[i] = (k - 1) * (ways[i - 1] + ways[i - 2])
return ways[n - 1]