Jump Game

Najbardziej bezpośredni pomysł to odegrać to. Stań na indeksie 0 i po kolei wypróbuj każde miejsce lądowania, na które pozwala skok. Powtórz to samo dla każdego miejsca lądowania. Jeśli w którejkolwiek gałęzi dotrzesz do ostatniego indeksu, odpowiedzią jest true. Jeśli każda gałąź kończy się ślepym zaułkiem, odpowiedzią jest false.

W pierwszym przykładzie indeks 0 zawiera 2, więc wypróbowujesz indeks 1 i indeks 2. Indeks 1 zawiera 0, czyli ślepy zaułek, więc cofasz się i wypróbowujesz indeks 2. Indeks 2 zawiera 3 i pozwala dotrzeć do indeksu 5, czyli ostatniego indeksu, więc wyszukiwanie kończy się wynikiem true.

Wyszukiwanie jest poprawne, ponieważ sprawdza każdą trasę. Na tym polega też jego problem: nie zapamiętuje indeksu, który już sprawdziło, więc ponownie sprawdza ten sam indeks dla każdej trasy, która do niego prowadzi. Gdy odpowiedzią jest false, musi wykluczyć każdą trasę. W [4, 3, 2, 1, 0, 5] każdy indeks przed 0 pozwala dotrzeć do 0, co daje 8 różnych tras prowadzących do niego. Przy 30 takich indeksach istnieje ponad 500 milionów tras, a największe testy mają 10,000 elementów. Tak długa trasa powoduje też przepełnienie stosu wywołań w niektórych językach: Python domyślnie zatrzymuje się po 1,000 zagnieżdżonych wywołaniach.

Powyższe wyszukiwanie wciąż zadaje to samo pytanie: „czy indeks j może zakończyć?”. Odpowiedź dla j nigdy się nie zmienia, więc ustal ją raz i zapisz. Indeks nazywamy dobrym, jeśli można z niego dotrzeć do ostatniego indeksu. Ostatni indeks jest dobry. Każdy inny indeks i jest dobry, jeśli co najmniej jeden indeks, na który można z niego trafić — od i+1 do i+nums[i] — jest dobry.

Każdy indeks zależy tylko od indeksów po swojej prawej stronie, więc wypełniaj tablicę good od prawej do lewej. W pierwszym przykładzie indeks 5 jest dobry. Indeks 4 ma wartość 0, więc nie jest dobry. Indeks 3 prowadzi tylko do indeksu 4, który nie jest dobry. Indeks 2 prowadzi do indeksów 3, 4 i 5, a indeks 5 jest dobry, więc indeks 2 też jest dobry. Indeks 1 ma wartość 0, więc nie jest dobry. Indeks 0 prowadzi do indeksów 1 i 2, a indeks 2 jest dobry, więc odpowiedzią jest true.

Teraz każdy indeks jest rozstrzygany tylko raz, ale jego rozstrzygnięcie nadal może wymagać sprawdzenia do n komórek. W przypadku [9998, 9997, …, 1, 0, 7] z każdego indeksu można dotrzeć do 0, ale nie do żadnego indeksu za nim, więc każdy indeks sprawdza cały swój zakres i nie znajduje w nim niczego dobrego. Daje to około 5 × 10^7 sprawdzeń dla 10 000 elementów, a największe testy są skonstruowane właśnie w ten sposób. Ilość pracy rośnie proporcjonalnie do kwadratu długości, więc ten algorytm nie mieści się w limicie czasu dla tych testów.

Patrz na indeksy, do których możesz dotrzeć, a nie na trasy. Z indeksu i możesz trafić na dowolny indeks od i+1 do i+nums[i], bez żadnych luk. Gdy więc indeks i jest osiągalny, osiągalny jest też każdy indeks aż do i+nums[i]. Zacznij od samego indeksu 0 i dodawaj kolejne takie zakresy. Każdy nowy zakres zaczyna się wewnątrz bloku, który już masz, więc osiągalne indeksy zawsze tworzą jeden ciągły blok: [0, farthest].

Dlatego wystarczy jedna liczba. Przechodź przez kolejne indeksy i, od lewej do prawej. Dopóki i ≤ farthest, indeks i jest osiągalny, więc zwiększaj zakres, aktualizując farthest do max(farthest, i+nums[i]). Jeśli i kiedykolwiek przekroczy farthest, żaden osiągalny indeks nie pozwala dotrzeć do i. Blok nie może powiększyć się przez tę lukę, więc żaden indeks na prawo od niej nie jest osiągalny, włącznie z ostatnim indeksem. Jeśli przejdziesz do końca bez napotkania luki, ostatni indeks jest osiągalny.

W drugim przykładzie farthest wynosi 0, potem 1 po indeksie 0, a następnie 4 po indeksie 1. Indeksy 2, 3 i 4 zawierają 0, więc jego wartość pozostaje równa 4. Indeks 5 leży za 4, więc odpowiedź to false. W pierwszym przykładzie indeks 2 zwiększa wartość farthest do 5 i żaden indeks nigdy jej nie przekracza, więc odpowiedź to true.

Dlaczego bezpiecznie jest przechowywać tylko największy zasięg? Nie decydujesz się na żaden konkretny skok. Blok zawiera każdy indeks osiągalny z dowolnej trasy, a każde krótsze miejsce lądowania znajduje się w jego obrębie. Odrzucenie wszystkich informacji poza prawym końcem nie powoduje utraty żadnych danych.