Dijkstra(SSSP): O((V-1)logV) * sqrt(2V)

V = 1 + .. + n = (n)(n+1)/2

그래프가 트리이므로 stage가 명확하다. 따라서 다익스트라를 굳이 사용하지 않고 직접 DP Design을 하는 게 간결하다.

n = len(triangle)

stage t: list row = tree level 0~n (n은 dummy)

state i: list column 0~t-1

ret func: f(t, i) = t~n단계에서 cost 합

BE: f(t, i) = triangle[t][i] + max{f(t+1, i), f(t+1, i+1)}

BC: f(n, i) = 0

Obj: f(0, 0)