Solução

Um problema de aplicação direta de programação dinâmica.

Vamos chamar $$dp_{ij}$$ de melhor solução partindo da linha $$i$$ e coluna $$j$$.

A partir disso podemos achar a recursão:

$$dp_{ij} = max(dp_{i+1, j}, dp_{i+1, j+1}) + v_{ij}$$

O que podemos ver nessa recurção, é que, a melhor solução partindo de um certo ponto é o valor daquele ponto, mais o valor máximo partindo de um dos pontos sob ele.

Assim computando recursivamente podemos achar a solução em $$O(n^2)$$, que passa no tempo.

Código:

https://gist.github.com/fredbr/a87dafa945ae9a0475920aa4059a2f58