作者cutekid (可爱小孩子)
看板Python
标题Re: [问题] list中选取最小和
时间Mon Nov 12 21:19:42 2018
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很大的时候会产生记忆体不足的现象
: 因此请教各位大大有没有更好的写法？
: 感谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.168.16.234
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1542028785.A.CB1.html
1F：推 yoyololicon: 漂亮喔 11/12 21:23
2F：推 ckc1ark: space还可以再reduce成O(1) 11/13 11:21
3F：推 chun10396974: 太强了 感谢!! 11/13 12:22
4F：→ cutekid: 推 ck 大说的: 类似求 fibnoacci number 三个变数的做法 11/13 12:24
5F：推 jlhc: 给推 11/13 13:50