題目是這樣的 給定一個都是數字的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很大的時候會產生記憶體不足的現象
因此請教各位大大有沒有更好的寫法？
感謝！