Oto pytanie, na które natknąłem się na forum wywiady:
Macie tablicę wypełnioną zerami i 1. 0 oznacza płonącą lawę, a a 1 oznacza odskocznię. Zaczynasz od początku array, a chcesz znaleźć najszybszy sposób na osiągnięcie końca. W każdym krok czasu możesz zwiększyć lub zmniejszyć swoją prędkość V o 1, lub możesz odskoczyć do kroku V o krok. Chcesz dotrzeć koniec tablicy bez przestojów.
Jaki jest dobry algorytm do rozwiązania tego problemu?
Próbowałem kilku rzeczy (głównie przy użyciu programowania dynamicznego i rekursji), ale nie mogłem wymyślić optymalnej podstruktury, która prowadziłaby do algorytmu nieliniowego. Jakieś pomysły?
Odpowiedzi:
1 dla odpowiedzi № 1Na każdym kroku masz dwie możliwości: zwiększanie prędkości lub nie zwiększanie prędkości. Następnie, dla każdej z tych opcji, kończysz na innym etapie i wybór powtarza się. Być może widzisz pojawiający się tutaj wzór drzewa. Każdy węzeł w drzewie jest krokiem i każda krawędź jest wyborem. Każdy węzeł (krok) ma dwie krawędzie (wybory), więc jest drzewem binarnym.
Zauważ także, że jeśli jesteś krok x z prędkością V, to nie ma znaczenia, jak się tam dostałeś, wynik tego, co nastąpi będzie taki sam, więc możesz trochę zoptymalizować (na przykład używając programowania dynamicznego).
Metoda brute-force mogłaby po prostu wyobrazić sobie to drzewo i wykonać dogłębne wyszukiwanie, dopóki dokładnie nie osiągniesz końcowego etapu. Może być wiele rozwiązań, a najszybszy temu rozwiązanie.
1 dla odpowiedzi nr 2
Programowanie dynamiczne jest odpowiednie podejście tutaj.
Dwuwymiarowy jest Twój obszar wyszukiwania: bieżąca pozycja jest pierwszym wymiarze, a aktualna prędkość jest drugi wymiar.Oznacza to, że potrzebujesz tablicę 2D best[N][N], gdzie N jest liczba elementów w tablicy boolean. Wartość w best[s,v] Reprezentuje najmniejszą liczbę czynności wymaganych do osiągnięcia pozycji s z prędkością v. Należy sprawdzić, czy każdy punkt przestrzeni wyszukiwania, aby sprawdzić, jeśli odskocznią można dojechać z aktualna prędkość.Jeśli odpowiedź brzmi "tak", ustawić odpowiednie miejsce w przestrzeni wyszukiwania.Również ustawić punkty dla sąsiadujących prędkości. Odpowiedź będzie w położeniu best[N-1][0].