作者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/m.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