数列中几个非相邻数相加比较取最大值

Question

一个数列有n个数，不能取相邻的数，比较并取出任意非相邻数相加的最大值

Answer 1

状态压缩，用0或1表示是否取某个数，然后再过滤出非相邻的组合，取最大值

nums = [3,1,4,1,5,9,2,6]
n = len(nums)
dp = [0]*2**n
x = 1
for i in range(n):
    for j in range(2**i):
        dp[x+j]=dp[j]+nums[i]
    x += j+1
res = [j for i, j in enumerate(dp) if "11" not in bin(i)]
print(max(res))