def ans(arr):
if(len(arr) < 2): return arr[0]
f = arr[:2]
for i in range(2,len(arr)):
f.append(arr[i] + min(f[-2],f[-1]))
return min(f[-2],f[-1])
print(ans([10,12,7,21,8]))
print(ans([155,44,52,58,250,225,109,178]))
※ 引述《chun10396974 (pulse6974)》之铭言：
: 题目是这样的 给定一个都是数字的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很大的时候会产生内存不足的现象
: 因此请教各位大大有没有更好的写法？
: 感谢！