整数划分问题python

动态规划，

设计一个算法，给出整数N，算法应该输出划分方案的总数，如果不存在这样的划分，则输出0

 

def cutting_count(arr):
    dyn=[0 for i in range(100)]
    n=len(arr)
    s=n*(n+1)/2#等差数列前N向求和
    if (s%2):#因为要把总和分成两个相等求和的集合，因此总和必须能被2整出，否则一个方法也找不到
        print(0)
        return
    s=int(s//2)
    dyn[0]=1#输入0时肯定只有一种分法
    for i in range(1,n+1):
        for j in range(s,i-1,-1):
            dyn[j]+=dyn[j-i]##dyn[j-i]表示加起来等于j-i的划分组数
    return dyn[s]//2
if __name__=='__main__':
    n=int(input())
    arr=[i for i in range(n)]
    count=cutting_count(arr)
    print(count)