Solução por Pedro Racchetti
Conhecimentos utilizados:
Para esse problema, temos que primeiro notar que, para qualquer resposta, podemos sempre transformar os caminhos de forma que o caminho de ida nunca esteja estritamente abaixo e a esquerda do caminho de volta, já que as mesmas ruas serão atravessadas, e os mesmos quarteirões serão cercados. Isso nos ajuda, pois agora podemos considerar que o caminho de ida irá somar na resposta todos os quarteirões que estão abaixo dele, e o de volta irá subtrair os quarteirões, ou seja, no final estaremos apenas somando os quarteir!oes entre os caminhos! Podemos fazer isso de forma rápida, pré-calculando as somas de prefixo em uma coluna, indo de baixo para cima. Chamaremos esses vetores de $$pref[i][j]$$, guardando a soma de quarteirões posicionados abaixo $$j$$, na $$i$$-ésima coluna + $$A_{i,j}$$.
Podemos então aplicar programação dinâmica, com duas recursões, de forma que uma calcule o melhor caminho de ida ($$DP_{ida}$$), e uma que calcule o melhor caminho de volta ($$DP_{volta}$$), com os estados sendo a posição atual. Note que como os valores são sempre positivos, a segunda recursão sempre escolherá um caminho de volta válido, como descrito anteriormente. As equações de transição são as seguintes:
- $$DP_{ida}(x, y) = max(DP_{ida}(x,y+1) + pref[x][y] – H_{x,y},$$ $$DP_{ida}(x+1,y) – V_{x,y})$$, já que essa recursão pode escolher ir para a direita, somando uma nova coluna ou descer.
- $$DP_{volta}(x, y) = max(DP_{volta}(x,y+1) – pref[x][y] – H_{x,y},$$ $$DP_{ida}(x+1,y) – V_{x,y})$$, já que essa recursão pode escolher ir para a direita, somando uma nova coluna ou descer.
A base para ambas as recursões, a base está em $$x = n$$ e $$y = m$$, onde ambas valem zero, já que não há o que adicionar. A resposta final é $$DP_{ida}(0,0) – DP_{volta}(0,0)$$
Segue o código, comentado, para melhor compreensão.
https://gist.github.com/PedroRacchetti/617285f90adcb1e798dfbc1ab65ca939