House Robber: rekurencja wybierz albo pomiń
Zamodelują Państwo decyzję rab/skip jako rekurencję DP, zmniejszą zużycie pamięci do dwóch zmiennych i rozszerzą rozwiązanie na domy ułożone w okrąg.
House Robber: rekurencja wybierz albo pomiń to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem rabowania domów
Problem rabowania domów polega na znalezieniu, w tablicy nieujemnych liczb całkowitych reprezentujących ilość pieniędzy w każdym domu, maksymalnej kwoty, którą można ukraść bez rabowania dwóch sąsiednich domów. Na przykład [2, 7, 9, 3, 1] daje wynik 12 (rabujemy domy 0, 2 i 4). Jest to klasyczny problem DP 1D, w którym na każdym kroku podejmowana jest decyzja binarna.
nums = [2, 7, 9, 3, 1]
# Can't rob adjacent houses
# Options: rob index 0 and 2 and 4 → 2+9+1=12
# or rob index 1 and 3 → 7+3=10
print('Max profit:', 12) # answer is 12Definiowanie rekurencji
Niech dp[i] oznacza maksymalną kwotę zrabowaną z pierwszych i+1 domów. W przypadku każdego domu i mamy dwie możliwości: pominąć go (wybrać dp[i-1]) albo zrabować go (wybrać nums[i] + dp[i-2]). Rekurencja ma postać dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Jest to podstawowy wzorzec „weź lub pomiń”, który pojawia się w wielu problemach DP.
# Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# Base cases:
# dp[0] = nums[0] (only one house, rob it)
# dp[1] = max(nums[0], nums[1]) (take the richer of the two)
def rob(nums):
n = len(nums)
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
print(rob([2, 7, 9, 3, 1])) # 12Prześledzenie tablicy DP
Dla [2, 7, 9, 3, 1] prześledźmy tablicę: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. Ostateczna odpowiedź to dp[4] = 12. Ręczne prześledzenie tablicy potwierdza, że rekurencja poprawnie obsługuje zarówno wybór elementu, jak i jego pominięcie na każdej pozycji.
nums = [2, 7, 9, 3, 1]
dp = [0] * len(nums)
dp[0] = 2
dp[1] = max(2, 7) # 7
for i in range(2, len(nums)):
skip = dp[i-1]
take = nums[i] + dp[i-2]
dp[i] = max(skip, take)
print(f'dp[{i}] = max({skip}, {nums[i]}+{dp[i-2]}) = {dp[i]}')
print('Answer:', dp[-1])Zmniejszenie pamięci do O(1)
Tablica DP odwołuje się wyłącznie do dwóch poprzednich pozycji, dlatego całą tablicę można zastąpić dwiema zmiennymi: prev2 (wartość sprzed dwóch kroków) i prev1 (wartość sprzed jednego kroku). Po każdej iteracji przesuwamy je: prev2 = prev1 oraz prev1 = current. Zmniejsza to zużycie pamięci z O(n) do O(1), zachowując złożoność czasową O(n).
def rob_optimised(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2 = prev1
prev1 = curr
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12
print(rob_optimised([1, 2, 3, 1])) # 4Przypadki brzegowe
Zawsze należy testować rozwiązanie na przypadkach brzegowych: pustej tablicy (zwraca 0), tablicy jednoelementowej (zwraca ten element) oraz tablicy dwuelementowej (zwraca większy z dwóch elementów). Podczas rozmowy kwalifikacyjnej wspomnienie o tych przypadkach i ich obsługa świadczą o dokładności. Warunek if n == 1 zapobiega wyjściu poza zakres indeksów przy odwołaniu do nums[1] podczas obliczania dp[1].
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2, prev1 = prev1, curr
return prev1
print(rob([])) # 0
print(rob([5])) # 5
print(rob([3, 10])) # 10
print(rob([10, 3])) # 10Rabowanie domów II: domy w okręgu
W wariancie kołowym (LeetCode 213) domy są rozmieszczone na okręgu, przez co pierwszy i ostatni dom sąsiadują ze sobą. Nie można bezpośrednio zastosować rekurencji dla układu liniowego. Kluczowa obserwacja jest następująca: albo rabujemy pierwszy dom i pomijamy ostatni, albo pomijamy pierwszy i uwzględniamy ostatni. Algorytm rabowania domów dla układu liniowego uruchamiamy dla obu podtablic, a następnie wybieramy większy wynik.
def rob_linear(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
def rob_circular(nums):
if len(nums) == 1: return nums[0]
# Either include first (exclude last) or include last (exclude first)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(rob_circular([2, 3, 2])) # 3
print(rob_circular([1, 2, 3, 1])) # 4Dlaczego strategia zachłanna zawodzi w tym przypadku
Naiwna strategia zachłanna mogłaby polegać na rabowaniu zawsze domu o największej dostępnej wartości. Jednak zawodzi ona dla danych takich jak [2, 1, 1, 2]: wybiera dom 0 (wartość 2), a następnie dom 3 (wartość 2), uzyskując łącznie 4, podczas gdy rabowanie domów 0 i 2 daje również 3. Chwileczkę — w tym przypadku strategia zachłanna działa! Spróbujmy jednak [1, 3, 1, 3, 100]: strategia zachłanna wybiera 3 i 3 (indeksy 1 i 3), uzyskując 6, i pomija optymalne 1+1+100=102. DP jest konieczne, ponieważ lokalnie optymalne wybory nie gwarantują globalnego optimum.
# Greedy failure example
nums = [1, 3, 1, 3, 100]
# Greedy: pick max each step
# picks 3 (index 1), then 3 (index 3) → total 6
# DP optimal: pick 1 (index 0) + 1 (index 2) + 100 (index 4) → 102
def rob(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
print(rob(nums)) # 102Rozpoznawanie wzorca „weź lub pomiń”
Wzorzec „weź lub pomiń” można uogólnić poza problem rabowania domów. Za każdym razem, gdy podczas przeglądania tablicy na każdej pozycji wybiera się między uwzględnieniem bieżącego elementu (i pominięciem poprzedniego) a wykluczeniem go (i zachowaniem poprzedniego wyniku), mamy do czynienia z DP typu „weź lub pomiń”. Należy zwracać uwagę na ograniczenia takie jak brak dwóch sąsiednich elementów lub brak nakładających się przedziałów — są to sygnały do zastosowania tego wzorca.
# General take-or-skip template
def take_or_skip(values, gap=1):
'''Max sum where selected elements must be at least gap+1 apart.'''
n = len(values)
if n == 0: return 0
# dp[i] = best up to index i
dp = [0] * (n + gap)
for i in range(n):
take = values[i] + (dp[i - 1] if i >= 1 else 0)
skip = dp[i + gap - 1] if i + gap - 1 < len(dp) else 0
dp[i + gap] = max(skip, take)
return dp[-1]
print(take_or_skip([2, 7, 9, 3, 1])) # house robber-likeWariant problemu usuwania i zdobywania punktów
Usuwanie i zdobywanie punktów (LeetCode 740) polega na tym, że za każdą wybraną liczbę otrzymuje się num × count(num), ale trzeba usunąć wszystkie wystąpienia liczby num-1 i num+1. Problem ten bezpośrednio redukuje się do rabowania domów: należy zbudować tablicę earn[v] = v × count(v) dla wszystkich wartości, a następnie uruchomić na niej algorytm rabowania domów. Rozpoznawanie takich redukcji jest kluczową umiejętnością podczas rozmów kwalifikacyjnych.
from collections import Counter
def delete_and_earn(nums):
if not nums: return 0
count = Counter(nums)
max_val = max(nums)
# earn[v] = total points from taking all v's
earn = [v * count[v] for v in range(max_val + 1)]
# Now run house robber on earn
prev2, prev1 = 0, 0
for e in earn:
prev2, prev1 = prev1, max(prev1, e + prev2)
return prev1
print(delete_and_earn([3, 4, 2])) # 6 (take 3+3=no, take 4+2=6)
print(delete_and_earn([2, 2, 3, 3, 3, 4])) # 9 (take all 3s)Rabowanie domów III: drzewo binarne
W problemie Rabowanie domów III domy są rozmieszczone w drzewie binarnym. Nie można jednocześnie obrabować węzła i jego bezpośredniego rodzica. Należy zdefiniować funkcję pomocniczą zwracającą dwie wartości: rob(node) → (rob_root, skip_root). Jeśli rabujemy korzeń, sumujemy wartości pominięcia obu jego dzieci. Jeśli pomijamy korzeń, sumujemy lepszy wynik dla każdego dziecka. Jest to przejście DFS w kolejności postorder z decyzją „weź lub pomiń” w każdym węźle.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob_tree(root):
def dfs(node):
if not node: return (0, 0) # (rob, skip)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))
# Tree: 3 -> 2,3 -> None,3,None,1
root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob_tree(root)) # 7Złożoność i omówienie podczas rozmowy kwalifikacyjnej
Liniowy problem rabowania domów działa w czasie O(n) i przy zużyciu pamięci O(1) dzięki optymalizacji z dwiema zmiennymi. Wariant kołowy również działa w czasie O(n), ponieważ dwukrotnie wywołuje wersję liniową. Wariant dla drzewa działa w czasie O(n) i przy zużyciu pamięci O(h), gdzie h oznacza wysokość drzewa. Podczas rozmowy kwalifikacyjnej należy zawsze podać złożoność po napisaniu kodu i wspomnieć o optymalizacji pamięci — pokazuje to, że myśli Pan/Pani szerzej niż tylko o pierwszym działającym rozwiązaniu.
# Summary of complexities
# Linear House Robber:
# Time: O(n), Space: O(1) with two-variable trick
# Circular House Robber:
# Time: O(n), Space: O(1) (two passes)
# Tree House Robber:
# Time: O(n), Space: O(h) call stack
# Quick benchmark
import time
import random
nums = [random.randint(0, 100) for _ in range(10**6)]
start = time.time()
prev2 = prev1 = 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
print(f'1M elements in {time.time()-start:.3f}s, result={prev1}')Szybki test
Proszę sprawdzić, jak dobrze rozumieją Państwo zagadnienia Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: rekurencji „wybierz lub pomiń” dp[i] = max(dp[i-1], nums[i] + dp[i-2]), zmniejszania zużycia pamięci z O(n) do O(1) za pomocą dwóch zmiennych kroczących oraz rozszerzania tego wzorca na tablice kołowe i drzewa binarne. Następnie omówimy problemy Maximum Subarray i Maximum Product Subarray z użyciem algorytmu Kadane’a.
Często zadawane pytania
Czy lekcja „House Robber: rekurencja wybierz albo pomiń” jest bezpłatna?
Tak — pełny tekst „House Robber: rekurencja wybierz albo pomiń” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „House Robber: rekurencja wybierz albo pomiń”?
Zamodelują Państwo decyzję rab/skip jako rekurencję DP, zmniejszą zużycie pamięci do dwóch zmiennych i rozszerzą rozwiązanie na domy ułożone w okrąg. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „House Robber: rekurencja wybierz albo pomiń”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- House Robber: rekurencja wybierz albo pomiń
- Maksymalna podtablica i podtablica o maksymalnym iloczynie
- Word Break i dzielenie ciągu na segmenty
- Decode Ways i zliczanie ścieżek