TDPC A コンテスト

qiita.com

続き。

atcoder.jp

初めのコード

n = int(input())
p = [int(i) for i in input().split()]
ans = set()
v = 0

def rec(i):
    global v
    if i == n:
        ans.add(v)
        return
    v += p[i]
    rec(i+1)
    v -= p[i]
    rec(i+1)

rec(0)
print(len(ans))

単純に、引数を減らしてみた。 で、漸化式を立てる。

dp[i+1][j] := i 番目までで j ができるかどうか

この漸化式を立てると、

dp[i+1][j] = dp[i][j] || dp[i][j-p[i]]
ただし、dp[0][0] = True

となる。 よって、これをそのままコードにすれば良い。

n = int(input())
p = [int(i) for i in input().split()]

dp = [[False for j in range(sum(p)+1)] for i in range(n+1)]
dp[0][0] = True

for i in range(n):
    for j in range(sum(p)+1):
        dp[i+1][j] = dp[i][j-p[i]] or dp[i][j]
ans = 0
for i in range(sum(p)+1):
    if dp[n][i]:
        ans += 1
print(ans)

計算量は、O(n * sum(p)) なので、10の6乗ぐらいになって実行可能。

もっと早く漸化式を立てられば、いいかなぁと思った。