この問題は個目の荷物の重さが,価値がであり,許容重量がである ナップサック問題に帰着できます.
時間計算量はで,この問題の制約下では十分高速です.
def make_vec(*dims, initial=0): n = len(dims) code = "[" * n + "{}] * {}" + " for _ in range({})]" * (n - 1) return eval(code.format(initial, *reversed(dims))) def div(n): res=[] i=int(1) while i*i<=n: if n%i==0: res.append(i) if n!=i**2: res.append(n//i) i+=1 res.sort() return res n=int(input()) A=[] for x in range(1,n+1): A.append(len(div(x))) dp=make_vec(n+1,n+1) for i in range(1,n+1): for j in range(n+1): if dp[i-1][j]==0 and j!=0: continue dp[i][j]=max(dp[i][j],dp[i-1][j]) if i+j<=n: dp[i][j+i]=max(dp[i][j+i],dp[i-1][j]+A[i-1]) print(dp[n][n])
解説とは関係ないですが「正整数を正の奇数の和に分解する場合の数」と 「正整数を相異なる正整数の和に分解する場合の数」は一致するらしいです.