Python динамическое программирование

Здаров гики и почти гики, только только начал изучать динамическое программирование, это моя первая задача на эту тему, до этого только прочитал 1 сайт и понял суть. Итак, вот ссылка на задачу: http://acm.timus.ru/problem.aspx?space=1&num=1017
Вот код:
k=int(input())
a=[]
a.append(0)
a.append(1)
a.append(1)
a.append(2)
a.append(2)
s=0
for j in range(5,k+1):
if j%2==1:
for i in range(1,j//2+1):
s+=a[i]
a.append(s)

else:
for i in range(1,j//2):
s+=a[i]
s=s+a[j//2]-1
a.append(s)
s=0
print(a)