編程挑戰幫助（python）？

-3

我正試圖解決項目歐勒問題18/67。我有an attempt但它不正確。編程挑戰幫助（python）？

tri = '''\ 
    75 
    95 64 
    17 47 82 
    18 35 87 10 
    20 04 82 47 65 
    19 01 23 75 03 34 
    88 02 77 73 07 63 67 
    99 65 04 28 06 16 70 92 
    41 41 26 56 83 40 80 70 33 
    41 48 72 33 47 32 37 16 94 29 
    53 71 44 65 25 43 91 52 97 51 14 
    70 11 33 28 77 73 17 78 39 68 17 57 
    91 71 52 38 17 14 91 43 58 50 27 29 48 
    63 66 04 68 89 53 67 30 73 16 69 87 40 31 
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23''' 
sum = 0 
spot_index = 0 

triarr = list(filter(lambda e: len(e) > 0, [[int(nm) for nm in ln.split()] for ln in tri.split('\n')])) 
for i in triarr: 
    if len(i) == 1: 
     sum += i[0] 
    elif len(i) == 2: 
     spot_index = i.index(max(i)) 
     sum += i[spot_index] 
    else: 
     spot_index = i.index(max(i[spot_index],i[spot_index+1])) 
     sum += i[spot_index] 

print(sum)

當我運行該程序時，總是有點偏離正確的總和/輸出應該是什麼。我很確定這是一個算法問題，但我不知道如何解決它或者最初的問題的最佳方法。

來源

2013-05-14 Swarage

將你的代碼粘貼到這裏。僅允許在外部鏈接中使用代碼的問題是不允許的。 –

你的算法如何找到最佳路徑？它看起來好像只是從頂端向下的最大數量。 – Blender

從底部開始 – James

這裏是算法。我會讓你找出一種方法來編碼它。

從下面兩行開始。在下一行的每個元素處，通過添加底行的兩個元素的最大值（對應於下一行的當前元素），計算出到達該元素後的總和。例如，根據上面的示例，下一行最左邊的元素是63，如果您到達該元素，您肯定會選擇其右側的子元素62.因此，您可以替換下一個元素中的63對於63 + 62 = 125的行到下一行。對下一行的每個元素執行相同的操作;你會得到125,164,102,95,112,123,165,128,166,109,112,147,100,54。現在刪除最下面的一行並在縮小的三角形上重複。

還有一種自頂向下的算法，它與上面給出的算法是雙重的。我也會讓你弄清楚。

來源

2013-05-15 03:08:08 user448810

您的算法錯誤。考慮下面一行是否有像1000000這樣的大數字。你的算法可能會遵循一條根本找不到它的路徑。

這個問題提示，這個可以被強行強制，但也有一個更聰明的方法來解決它。

不知何故，你的算法將需要考慮全部可能的路徑/總和。

蠻力法是從上到下嘗試每一個。

聰明的方法使用了一種叫做動態編程的技巧

來源

2013-05-14 22:37:43

編程挑戰幫助（python）？

回答

相關問題