House Robber

Q: Jaka jest zależność rekurencyjna dla problemu House Robber?

Najlepsza suma z pierwszych k domów to max(best[k-1], best[k-2] + nums[k-1]) . Albo pomijasz dom k-1 i zachowujesz najlepszy wynik z wcześniejszych domów, albo wybierasz dom k-1 i dodajesz jego wartość do najlepszego wyniku kończącego się przed jego sąsiadem. Przypadki bazowe to 0 dla braku domów i nums[0] dla jednego domu.

Q: Dlaczego wybieranie co drugiego domu nie rozwiązuje problemu włamywacza?

Najlepszy plan czasem pomija dwa domy z rzędu. W [10, 1, 1, 10] suma wartości domów o parzystych i nieparzystych indeksach wynosi 11, natomiast wybranie pierwszego i ostatniego domu daje 20. Programowanie dynamiczne porównuje pominięcie domu z jego wybraniem dla każdego domu, dzięki czemu znajduje takie plany.

ŚrednieProgramowanie dynamiczne

+10

Domy stoją w rzędzie wzdłuż ulicy, a nums[i] to kwota pieniędzy w domu i. Możesz zabrać pieniądze z dowolnie wybranych domów, ale nigdy z dwóch sąsiadujących ze sobą. Zwróć największą sumę, jaką możesz zabrać.

Funkcja

rob(nums: integer-array) → integer

numsinteger-array: pieniądze w każdym domu, w kolejności wzdłuż ulicy
Zwracainteger: największa łączna kwota, jaką możesz zabrać, nie zabierając pieniędzy z dwóch sąsiadujących domów

Ograniczenia

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
Odpowiedź wynosi co najwyżej 5 × 10⁶, więc mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: nums = [5, 3, 4, 11, 2]
Wyjście: 16
Wyjaśnienie: Weź 5 i 11 z domów 0 i 3, aby uzyskać 16. Możesz pominąć dwa domy z rzędu i w tym przypadku jest to lepsze niż każdy inny plan: 5 + 4 + 2 = 11, a 3 + 11 = 14.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Zwróć domy do zabrania oraz ich łączną liczbę. Co musisz zachować z tabeli, aby odtworzyć tę listę, i czy dwie bieżące sumy nadal wystarczą?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Oczywiste skróty zawodzą. Wybieranie co drugiego domu pomija plany, które omijają dwa domy z rzędu, jak 5 i 11 w [5, 3, 4, 11, 2], a wybranie najbogatszego domu w pierwszej kolejności nie sprawdza się dla [3, 4, 3], gdzie 4 blokuje dwa domy warte łącznie 6. Działa podejmowanie decyzji po jednym domu naraz: najlepsza suma do danego domu zależy tylko od najlepszych sum do dwóch domów przed nim.

Wypróbuj obie opcje przy każdym domu

Poprawne, ale nie kończy się na największych testach

Intuicja

Spójrz na ostatni dom, dom n-1. Każdy plan albo go pomija, albo go wybiera. Jeśli go pomija, najlepsze, co może zrobić, to wybrać najlepszy plan dla pierwszych n-1 domów. Jeśli go wybiera, dom n-2 jest niedostępny, więc dodaje nums[n-1] do najlepszego planu dla pierwszych n-2 domów. Odpowiedzią jest większa z tych dwóch wartości.

Zapiszmy to jako funkcję most(k), czyli maksymalną wartość, jaką możesz uzyskać z pierwszych k domów: most(k) = max(most(k-1), most(k-2) + nums[k-1]), przy czym most(0) = 0 dla braku domów i most(1) = nums[0] dla jednego domu. Każdy plan pomija albo wybiera swój ostatni dom, więc te dwie gałęzie obejmują wszystkie plany, a wynik jest poprawny.

To działa wolno, ponieważ gałęzie się nakładają. most(k-1) ponownie wywołuje most(k-2), więc na to samo pytanie odpowiada się raz za razem, a liczba wywołań rośnie jak liczby Fibonacciego, w przybliżeniu 1.6^n. Już 40 domów wymaga ponad 300 milionów wywołań, a testy obejmują do 10^4 domów. Wywołania zagnieżdżają się też na głębokość n poziomów, przekraczając domyślny limit Pythona wynoszący 1000.

Algorytm

Napisz funkcję pomocniczą most(k), która zwraca największą kwotę, jaką możesz zabrać z pierwszych k domów.
Zwróć 0, gdy k wynosi 0, i nums[0], gdy k wynosi 1.
W przeciwnym razie oblicz skip = most(k-1) i take = most(k-2) + nums[k-1].
Zwróć większą z tych dwóch wartości. Odpowiedzią jest most(n).

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

Tablica budowana od dołu

Intuicja

Rekurencja pyta tylko o most(0) aż do most(n), więc istnieje n + 1 różnych pytań. Odpowiedz na każde z nich raz, zapisz odpowiedź w tabeli i wypełniaj tabelę w takiej kolejności, aby każda odczytywana odpowiedź już się w niej znajdowała. Tabelę definiują cztery decyzje.

Stan: best[k] to najwięcej, ile możesz zabrać z pierwszych k domów. Rekurencja: best[k] = max(best[k-1], best[k-2] + nums[k-1]): pomiń dom k-1 albo go okradnij, dodając jego wartość do najlepszego wyniku dla domów przed jego sąsiadem. Przypadki bazowe: best[0] = 0 i best[1] = nums[0]. Kolejność: k od 2 do n, ponieważ każdy element odczytuje dwa poprzednie.

Dla [5, 3, 4, 11, 2] tabela ma wartości 0, 5, 5, 9, 16, 16. Dla k = 4 porównujesz pominięcie domu 3, warte best[3] = 9, z okradnięciem go i dodaniem jego 11 do best[2] = 5; wygrywa 16. Odpowiedzią jest ostatni element. Obliczenie każdego elementu wymaga jednego porównania, więc czas działania wynosi O(n), a tabela zajmuje O(n) pamięci.

Algorytm

Utwórz tablicę best z n + 1 elementami.
Ustaw best[0] = 0 i best[1] = nums[0].
Dla k od 2 do n ustaw best[k] na większą z wartości best[k-1] i best[k-2] + nums[k-1].
Zwróć best[n].

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

Dwie sumy bieżące

Intuicja

Każdy wpis w tabeli odczytuje tylko dwa wpisy bezpośrednio przed nim. Gdy znana jest wartość best[k], best[k-2] nie jest już odczytywana. Zamiast tabeli wystarczą więc dwie liczby: twoBack, najlepszy wynik dla domów do dwóch pozycji wstecz, oraz oneBack, najlepszy wynik do poprzedniego domu.

Dla domu zawierającego x nowy najlepszy wynik to max(oneBack, twoBack + x). Następnie przesuwamy wartości: twoBack przyjmuje poprzednią wartość oneBack, a oneBack przyjmuje nowy najlepszy wynik. Obie zaczynają od 0, co oznacza pustą ulicę przed pierwszym domem, więc pierwszy dom nie wymaga osobnego przypadku: jego najlepszy wynik to max(0, 0 + nums[0]).

Dla [5, 3, 4, 11, 2] para przyjmuje kolejno wartości (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), a na końcu oneBack ma wartość 16. Nakład pracy jest taki sam jak w przypadku tabeli: O(n), a zużycie pamięci spada do O(1).

Algorytm

Ustaw twoBack i oneBack na 0.
Dla każdej kwoty x w nums oblicz current = max(oneBack, twoBack + x).
Przenieś oneBack do twoBack, a następnie current do oneBack.
Po ostatnim domu zwróć oneBack.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika ze skrótu, który działa dla małych danych wejściowych, albo z aktualizowania dwóch sum w niewłaściwej kolejności.

Sumowanie parzystych i nieparzystych domów, a następnie wybieranie większej sumy, nie uwzględnia planów pomijających dwa sąsiadujące domy. Dla [10, 1, 1, 10] obie sumy wynoszą 11, ale domy 0 i 3 dają 20.
Wybieranie najbogatszego domu jako pierwszego nie sprawdza się dla [3, 4, 3]: wybierasz 4 i blokujesz oba domy z 3, które razem dają 6.
Nadpisanie oneBack przed skopiowaniem go do twoBack powoduje utratę wartości potrzebnej dla następnego domu. Najpierw oblicz nową najlepszą wartość, a potem przesuń wartości albo przypisz obie naraz, jeśli pozwala na to język.
Odczytanie nums[1] lub ustawienie z góry best[1] i best[2] nie działa przy ulicy z jednym domem. Rozpoczęcie obu sum od 0 eliminuje ten szczególny przypadek.
W Lua i R tablice zaczynają się od 1, więc pieniądze w domu k-1 znajdują się w nums[k].

Najczęstsze pytania4

Jaka jest zależność rekurencyjna dla problemu House Robber?

Najlepsza suma z pierwszych k domów to max(best[k-1], best[k-2] + nums[k-1]). Albo pomijasz dom k-1 i zachowujesz najlepszy wynik z wcześniejszych domów, albo wybierasz dom k-1 i dodajesz jego wartość do najlepszego wyniku kończącego się przed jego sąsiadem. Przypadki bazowe to 0 dla braku domów i nums[0] dla jednego domu.

Jaka jest złożoność czasowa i pamięciowa problemu House Robber?

Rozwiązanie z programowaniem dynamicznym odwiedza każdy dom raz, więc działa w czasie O(n). Pełna tablica zajmuje O(n) pamięci, a przechowywanie tylko dwóch ostatnich sum zmniejsza tę wartość do O(1). Zwykła rekurencja bez zapisywania wyników wykonuje około 1.6^n wywołań, co oznacza złożoność wykładniczą.

Dlaczego wybieranie co drugiego domu nie rozwiązuje problemu włamywacza?

Najlepszy plan czasem pomija dwa domy z rzędu. W [10, 1, 1, 10] suma wartości domów o parzystych i nieparzystych indeksach wynosi 11, natomiast wybranie pierwszego i ostatniego domu daje 20. Programowanie dynamiczne porównuje pominięcie domu z jego wybraniem dla każdego domu, dzięki czemu znajduje takie plany.

Jak rozwiązać problem rabusia okradającego domy, gdy domy tworzą okrąg?

Na okręgu pierwszy i ostatni dom są sąsiadami, więc plan może uwzględniać najwyżej jeden z nich. Uruchom rozwiązanie dla prostej ulicy dwa razy: raz bez ostatniego domu, a raz bez pierwszego, i zwróć większy wynik. Ulica z jednym domem to szczególny przypadek: odpowiedzią jest ten dom.