House Robber

Q: Dlaczego okradanie co drugiego domu nie rozwiązuje problemu rabusia domów?

Najlepszy plan czasami pomija dwa domy z rzędu. W [10, 1, 1, 10] suma wartości domów o parzystych i nieparzystych indeksach wynosi 11, a pierwszego i ostatniego domu — 20.

ŚrednieProgramowanie dynamiczne

+10

Domy stoją 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 okradając dwóch sąsiadujących domów

Ograniczenia

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
Wynik jest nie większy niż 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żna pominąć dwa domy z rzędu, a w tym przypadku ten plan przewyższa wszystkie pozostałe: 5 + 4 + 2 = 11 i 3 + 11 = 14.

Pytanie dodatkowe

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

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Skróty zawodzą: wybieranie co drugiego domu oznacza pominięcie 5 i 11 w [5, 3, 4, 11, 2], a wybranie najbogatszego domu jako pierwszego daje gorszy wynik dla [3, 4, 3]. Zamiast tego rozpatruj po jednym domu naraz: najlepsza suma do danego domu zależy tylko od najlepszych sum do dwóch poprzednich domów.

Wypróbuj oba wybory w każdym domu

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

Intuicja

Każdy plan albo pomija ostatni dom, albo go wybiera. Pominięcie pozostawia najlepszy plan dla pierwszych n-1 domów; wybranie dodaje nums[n-1] do najlepszego planu dla pierwszych n-2 domów. Zatem most(k) = max(most(k-1), most(k-2) + nums[k-1]), przy czym most(0) = 0 i most(1) = nums[0]. Te dwie gałęzie obejmują wszystkie plany, więc odpowiedź jest poprawna.

Gałęzie nakładają się: most(k-1) ponownie oblicza most(k-2), a liczba wywołań rośnie jak liczby Fibonacciego, czyli w przybliżeniu 1.6^n. Dla czterdziestu domów potrzeba ponad 300 milionów wywołań, a n osiąga 10^4.

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, a 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))

Tabela budowana od dołu

Intuicja

Rekurencja pyta tylko o most(0) do most(n): n + 1 pytań. Odpowiedz na każde pytanie raz, zapisując wynik w tablicy best, zaczynając od best[0] = 0 i best[1] = nums[0], a następnie wypełniając ją w górę od k = 2, tak aby oba wpisy odczytywane przy każdym pytaniu były już dostępne.

Dla [5, 3, 4, 11, 2] tablica ma wartości 0, 5, 5, 9, 16, 16. Przy k = 4 pominięcie domu 3 daje best[3] = 9, natomiast wzięcie jego 11 i dodanie do best[2] = 5 daje 16, co wygrywa. Każdy wpis wymaga jednego porównania: czas O(n) i pamięć O(n).

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 odczytuje tylko dwa poprzedzające go wpisy, więc zamiast tablicy przechowuj dwie liczby: twoBack i oneBack — najlepsze sumy odpowiednio do domu sprzed dwóch domów i do poprzedniego domu. Dla domu o wartości x nowa najlepsza suma to max(oneBack, twoBack + x); następnie przesuń obie wartości. Obie zaczynają od 0, czyli od pustej ulicy przed pierwszym domem, więc ulica z jednym domem nie wymaga specjalnego przypadku. Czas działania nadal wynosi 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

Nadpisywanie oneBack przed skopiowaniem go do twoBack. Następny dom odczytuje wtedy nieprawidłową sumę. Najpierw oblicz nową najlepszą wartość, a potem przesuń wartości albo przypisz obie naraz.
Odczytywanie nums[1] lub ustawianie best[1] i best[2] na początku. Oba rozwiązania zawodzą na ulicy z jednym domem, takiej jak [0].
W Lua i R tablice zaczynają się od 1, więc pieniądze w domu k-1 znajdują się w nums[k].

Najczęstsze pytania3

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

Programowanie dynamiczne analizuje każdy dom jeden raz, więc działa w czasie O(n). Pełna tablica zajmuje O(n) miejsca, 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ń.

Dlaczego okradanie co drugiego domu nie rozwiązuje problemu rabusia domów?

Najlepszy plan czasami pomija dwa domy z rzędu. W [10, 1, 1, 10] suma wartości domów o parzystych i nieparzystych indeksach wynosi 11, a pierwszego i ostatniego domu — 20.

Jak rozwiązać problem House Robber, gdy domy tworzą okrąg?

W okręgu pierwszy i ostatni dom są sąsiadami, więc plan obejmuje najwyżej jeden z nich. Uruchom rozwiązanie dla prostej ulicy dwa razy: raz bez ostatniego domu i raz bez pierwszego, a następnie zwróć większy wynik. Jeden dom to przypadek szczególny: odpowiedzią jest ten dom.