31 lines
553 B
Python
31 lines
553 B
Python
#!/usr/bin/env python3
|
|
|
|
# p -> recursive with lookup table
|
|
# p2 -> count individual combs, add squares, got from forum
|
|
|
|
def p(n, tbl=False):
|
|
if n < 3:
|
|
return 1
|
|
if tbl==False:
|
|
tbl = []
|
|
if n-3 >= len(tbl):
|
|
r = 2*p(n-1, tbl) - p(n-2,tbl) + p(n-4, tbl)
|
|
tbl.append(r)
|
|
return tbl[n-3]
|
|
|
|
def p2(n):
|
|
if n < 3:
|
|
return 1
|
|
rd = 1
|
|
b1 = b2 = 0
|
|
b3 = 1
|
|
for i in range(3,n):
|
|
b = b3
|
|
b3 += b2
|
|
b2 = b1
|
|
b1 = rd
|
|
rd += b
|
|
return rd+b1+b2+b3
|
|
|
|
print(p(50))
|