17 lines
462 B
Python
17 lines
462 B
Python
|
|
def expand(limit):
|
|
lst = [0] * (limit + 1)
|
|
for cur in range(2, limit + 1):
|
|
simple = lst[cur - 1]
|
|
root = int(cur ** 0.5)
|
|
if root ** 2 == cur:
|
|
simple = min(simple, lst[root])
|
|
if not cur % 2:
|
|
simple = min(simple, lst[cur // 2])
|
|
for half in range(2, (cur + 1) // 2):
|
|
simple = min(simple, lst[half] + lst[cur - half])
|
|
lst[cur] = simple + 1
|
|
return lst
|
|
|
|
print(expand(15))
|