# Tricky Triangularization

A root path is a path in a triangular lattice which contains exactly one vertex in each row.

What is the maximum sum of the numbers on the vertices of a root path in this lattice of 500 rows?

Details and Assumptions

• For eg, in the following lattice, the vertex $$\color{blue}{5}$$ can only be connected to the $$\color{red}{\text{red}}$$ vertices in a root path.
$1\\\color{red}{2}\quad\color{red}{3}\\4\quad\color{blue} {5}\quad6\\7\quad\color{red}{8}\quad\color{red}{9}\quad 1$
• All neighbouring vertices must be connected with an edge.
• Explicit example of maximum sum root path, highlighted in red:

$\color{red}{3}\\ \color{red}{7}\quad 4\\ 2\quad \color{red}{4}\quad 6\\ 8\quad 5\quad \color{red}{9}\quad 3$

• Bruteforce is not the best idea because $$2^{499}$$ paths exist. An efficient solution can find the answer well under a second.

×