아래와 같은 삼각형의 꼭대기에서 인접한 수를 따라 내려가는 경로의 합을 계산해보면, 붉은 색으로 표시한 경우가 3 + 7 + 4 + 9 = 23으로 가장 큽니다.

3
7 4
2 4 6
8 5 9 3

텍스트 파일 triangle.txt (우클릭해서 다운로드)에는 100줄짜리 삼각형 수 데이터가 들어 있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최댓값은 얼마입니까?

참고: 이 문제는 18번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경우의 수가 모두 2⁹⁹ 이나 되기 때문입니다. 일 초에 1조 (10¹²)개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 200억년이 걸립니다. 이 문제를 해결할 수 있는 효율적인 알고리즘을 찾아보시기 바랍니다.