题目是这样的 给定一个都是数字的list
对于每个数字可以决定选或不选
但是不能有相邻的两个都没有被选到
example1:[10,12,7,21,8]
10+7+8=25
有最小值
example2:[155,44,52,58,250,225,109,178]
44+58+225+109=436
有最小值
刚开始以为是用数学方法来做
于是便以两个一组、三个一组、四个一组来讨论选取的方式
但是实际下去操作会发现前面怎么取都无法顾及到后面的选取
(因为不知道后面的数的大小关系)
即一定要顾虑到所有的数
所以改采recursive的方法来穷举
b=[]
def help_santa(a):
n=len(a)
plus(a,0,0,n)
return min(b)
def plus(a,s,t,n):
if n==0:
b.append(t)
elif s==1:
plus(a,0,t+a[-n],n-1)
else:
plus(a,0,t+a[-n],n-1)
plus(a,1,t,n-1)
其中函数的第二个值为1代表上一个被跳过所以下一个值必须要选
但是这个做法在输入的list很大的时候会产生内存不足的现象
因此请教各位大大有没有更好的写法？
感谢！