Project Euler：Problem 18/67

num = 
[[75],
[95,64],
[17,47,82],
[18,35,87,10],
[20,4,82,47,65],
#以下略
#Triangle(Problem18:373Byte)
#Triangle(Problem67:15250Byte)

st = num.length - 2
for i in 0..st
    n = st - i
    for j in 0..n
        num[n][j] += (num[n+1][j] + num[n+1][j+1] + (num[n+1][j] - num[n+1][j+1]).abs ) / 2
    end
end
puts num[0][0]

上からたどると，Problem18なら2の14乗で16384通り，Problem67なら2の99乗で633825300114114700748351602688通り． Problem18なら，まだBrute Forceが通用する量だが，Problem67でBrute Forceは使えない．というか，使うと終わらない． 仮に1G通り/s検証出来たとして，最大で約6*10^20秒，86400s/dayで一年365日が31436000秒．7桁落としたところで2*10^13年． ま，終わる頃には地球なんて無いですね．

故に逆から計算．大小比較して大きい方を上に加える．それの繰り返し．計算ステップが4950．激減です．

内側のfor文内部は，まぁ，ifで振り分けた方がわかりやすいかも知れない．

num[n][j] += num[n+1][j] if num[n+1][j] >= num[n+1][j+1]
num[n][j] += num[n+1][j+1] if num[n+1][j] < num[n+1][j+1]

みたいな．