[//]: # 分享一些从DFS改记忆化搜索再到DP的一些心得

暴力枚举

import time

A = [1 for _ in range(int(1e5)+1)]
def dfs(index,weight):
    global ans
    if(index >= N):
        if(weight > 0 and A[weight]):
            A[weight] = 0
            ans += 1
        return
    dfs(index+1,weight)

    dfs(index+1,weight-W[index])

    dfs(index+1,weight+W[index])

    return

ans = 0
N = int(input())
start = time.time()
W = list(map(int,input().split()))
dfs(0,0)
end = time.time()
print(ans)
print(end-start)

记忆化搜索

#这个加了记忆化搜索，速度大大提升，但N=100时用时大约11s左右，不能AC
N = int(input())
begin = time.time()
A = [1 for _ in range(int(1e5) + 1)]
W = list(map(int, input().split()))
su = sum(W)
dp = [[-1 for _ in range(2 * su + 1)] for _ in range(N + 1)]


def dfs(index, weight):
    global ans
    global dp
    if (dp[index][weight] != -1):
        return dp[index][weight]
    if (index >= N):
        if (weight > 0 and A[weight]):
            A[weight] = 0
            ans += 1
        return ans
    dp[index + 1][weight] = dfs(index + 1, weight)

    dp[index + 1][weight - W[index]] = dfs(index + 1, weight - W[index])

    dp[index + 1][weight + W[index]] = dfs(index + 1, weight + W[index])

    return


ans = 0
dfs(0, 0)
end = time.time()
print(ans)
print(end-begin)

改DP

#这个是自己改的DP,这种由记忆搜索改DP我感觉主要思路是考分析过程以及感觉，因为DFS时本质上计算ans是判断最后一层是否大于零，因此在
#改DP时考虑从上到下，一开始我改的时候用的是从下到上，因为上面记忆化搜索的时候的从下到上返回值的，但是做不出来，之后转换思路，想到
#之前也做过Y总的遍历最下层求答案类似的这种题，所以在结合上面DFS时求ans的方法，想到从上到下。
#之后做DP题要善于转换思路，从上到下和从下到上都要考虑一下，说不定会有惊喜。
import time
start = time.time()
N = int(input())
W = list(map(int,input().split()))
su = sum(W)
dp = [[0 for _ in range(2*su+1)] for _ in range(N+1)]
dp[0][0] = 1
# ans = 0

for index in range(1,N+1):
    for weight in range(-su,su+1):
            dp[index][weight] = dp[index-1][weight] | dp[index-1][weight-W[index-1]] | dp[index-1][weight+W[index-1]]
            # if(index == N and dp[index][weight] != 0 and weight > 0 and weight <= su):
            #     ans += 1
end = time.time()

# print(ans)
print(sum(dp[N][1:su+1]))
print(end-start)