Jump Game

A ideia mais direta é encenar o processo. Fique no índice 0 e tente, um por um, cada ponto de aterrissagem permitido pelo seu salto. A partir de cada ponto de aterrissagem, faça o mesmo novamente. Se algum ramo chegar ao último índice, a resposta é true. Se todos os ramos chegarem a um beco sem saída, é false.

No primeiro exemplo, o índice 0 contém 2, então você tenta os índices 1 e 2. O índice 1 contém 0, um beco sem saída, então você volta e tenta o índice 2. O índice 2 contém 3 e alcança o índice 5, o último índice, e a busca termina com true.

A busca está correta porque considera todas as rotas. Esse também é o seu problema: ela nunca se lembra de um índice que já explorou, então explora o mesmo índice novamente para cada rota que chega até ele. Quando a resposta é false, ela precisa descartar todas as rotas. Em [4, 3, 2, 1, 0, 5], todos os índices antes do 0 podem chegar ao 0, o que gera 8 rotas diferentes até ele. Com 30 índices desse tipo, há mais de 500 milhões de rotas, e os maiores testes têm 10,000 elementos. Uma rota tão longa também estoura a pilha de chamadas em algumas linguagens: por padrão, Python para após 1,000 chamadas aninhadas.

A busca acima faz a mesma pergunta, "o índice j consegue terminar?", repetidamente. A resposta para j nunca muda, então descubra-a uma vez e armazene-a. Chame um índice de bom quando for possível chegar dele ao último índice. O último índice é bom. Qualquer outro índice i é bom quando pelo menos um índice em que ele pode cair, de i+1 a i+nums[i], é bom.

Cada índice depende apenas dos índices à sua direita, então preencha uma tabela good da direita para a esquerda. No primeiro exemplo, o índice 5 é bom. O índice 4 contém 0, então não é. O índice 3 alcança apenas o índice 4: não é bom. O índice 2 alcança os índices 3, 4 e 5, e 5 é bom, então 2 é bom. O índice 1 contém 0: não é bom. O índice 0 alcança 1 e 2, e 2 é bom, então a resposta é true.

Agora cada índice é decidido uma única vez, mas para decidi-lo ainda pode ser necessário percorrer até n células. Em [9998, 9997, …, 1, 0, 7], cada índice pode alcançar o 0 e nada além dele, então cada um percorre todo o seu intervalo e não encontra nenhum índice bom. Isso dá cerca de 5 × 10^7 verificações para 10.000 elementos, e os maiores testes são construídos assim. O trabalho cresce com o quadrado do comprimento, então o tempo acaba antes que eles terminem.

Observe quais índices você consegue alcançar, não as rotas. A partir do índice i, você pode chegar a qualquer índice de i+1 a i+nums[i], sem lacunas. Portanto, quando o índice i é alcançável, todos os índices até i+nums[i] também são alcançáveis. Comece apenas com o índice 0 e continue adicionando esses trechos. Cada novo trecho começa dentro do bloco que você já tem, então os índices alcançáveis sempre formam um único bloco contínuo, [0, farthest].

Por isso, basta um número. Percorra i da esquerda para a direita. Enquanto i ≤ farthest, o índice i é alcançável, então amplie farthest para max(farthest, i+nums[i]). Se i ultrapassar farthest, nenhum índice alcançável chega a i. O bloco não pode crescer além dessa lacuna, então nenhum índice à direita dela é alcançável, incluindo o último índice. Se a varredura chegar ao fim sem lacunas, o último índice é alcançável.

No segundo exemplo, farthest é 0, depois 1 após o índice 0 e, em seguida, 4 após o índice 1. Os índices 2, 3 e 4 contêm 0 e mantêm o valor em 4. O índice 5 está além de 4, então a resposta é false. No primeiro exemplo, o índice 2 leva farthest a 5 e nenhum índice fica além dele, então a resposta é true.

Por que é seguro manter apenas o maior alcance? Você nunca se compromete com um salto. O bloco contém todos os índices que qualquer rota pode alcançar, e todos os pontos de chegada mais próximos ficam dentro dele. Descartar tudo, exceto a extremidade direita, não faz você perder nenhuma informação.