House Robber: rekurrens för ta eller hoppa över
Modellera beslutet att råna eller hoppa över som en DP-rekurrens, minska utrymmet till två variabler och utöka lösningen till cirkulära hus.
House Robber: rekurrens för ta eller hoppa över är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Problemet House Robber
Problemet House Robber frågar: givet en array med icke-negativa heltal som representerar penningbeloppet i varje hus, hitta det största beloppet du kan råna utan att råna två intilliggande hus. Till exempel ger [2, 7, 9, 3, 1] resultatet 12 (råna hus 0, 2 och 4). Detta är ett klassiskt 1D-DP-problem där du gör ett binärt val vid varje steg.
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 12Definiera rekurrensen
Låt dp[i] vara det största penningbeloppet som rånats från de första i+1 husen. Vid varje hus i har du två val: hoppa över det (ta dp[i-1]) eller råna det (ta nums[i] + dp[i-2]). Rekurrensen är dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Detta är det grundläggande ta-eller-hoppa-över-mönstret som förekommer i många DP-problem.
# 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])) # 12Gå igenom DP-tabellen
För [2, 7, 9, 3, 1] går vi igenom tabellen: 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. Det slutliga svaret är dp[4] = 12. Genom att gå igenom tabellen manuellt bekräftar du att rekurrensen hanterar både valet att ta och att hoppa över korrekt på varje position.
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])Minska minnesutrymmet till O(1)
DP-tabellen tittar bara tillbaka på två positioner, så vi kan ersätta hela arrayen med två variabler: prev2 (två steg bakåt) och prev1 (ett steg bakåt). Efter varje iteration flyttar vi dem: prev2 = prev1 och prev1 = current. Det minskar minnesåtgången från O(n) till O(1) samtidigt som tidskomplexiteten förblir 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])) # 4Randfall att hantera
Testa alltid lösningen mot randfall: en tom array (return 0), en array med ett enda element (returnera det elementet) och en array med två element (returnera det största av de två). I intervjuer visar det att du är noggrann om du nämner och hanterar dessa fall. Vakten if n == 1 förhindrar index utanför arrayens gränser när nums[1] används för 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])) # 10House Robber II: hus i en cirkel
Den cirkulära varianten (LeetCode 213) placerar husen i en cirkel, så att det första och sista huset ligger bredvid varandra. Du kan inte använda den linjära rekurrensen direkt. Den centrala insikten är: antingen rånar du det första huset och utesluter det sista, eller så utesluter du det första och inkluderar det sista. Kör den linjära House Robber-lösningen på båda delarrayerna och välj det största värdet.
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])) # 4Varför en girig algoritm misslyckas här
En naiv girig algoritm kan försöka råna det största tillgängliga huset varje gång. Det misslyckas dock för indata som [2, 1, 1, 2]: den giriga algoritmen väljer hus 0 (värde 2) och sedan hus 3 (värde 2), vilket ger summan 4, men att råna hus 0 och 2 ger också 3. Vänta — i det här fallet fungerar den giriga algoritmen! Men prova [1, 3, 1, 3, 100]: den giriga algoritmen väljer 3 och 3 (index 1 och 3), vilket ger 6, och missar det optimala 1+1+100=102. DP behövs eftersom lokalt optimala val inte garanterar ett globalt 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)) # 102Känna igen ta-eller-hoppa-över-mönstret
Ta-eller-hoppa-över-mönstret kan generaliseras bortom House Robber. Varje gång du går igenom en array och vid varje position väljer mellan att inkludera det aktuella elementet (och hoppa över det föregående) eller att utesluta det (och behålla det föregående resultatet), har du en ta-eller-hoppa-över-DP. Håll utkik efter begränsningar som inga två intilliggande element eller inga överlappande intervall — de är signaler på att detta mönster kan användas.
# 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-likeVarianten Delete and Earn
Delete and Earn (LeetCode 740) frågar: för varje tal du väljer får du num × count(num) poäng, men måste ta bort alla förekomster av num-1 och num+1. Detta kan direkt reduceras till House Robber: bygg en array earn[v] = v × count(v) för alla värden och kör sedan House Robber på denna array. Att känna igen sådana reduktioner är en viktig intervjufärdighet.
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)House Robber III: binärt träd
I House Robber III är husen ordnade som ett binärt träd. Du kan inte råna en nod och dess direkta förälder samtidigt. Definiera en hjälpfunktion som returnerar två värden: rob(node) → (rob_root, skip_root). Om du rånar roten summerar du de båda barnens skip-värden. Om du hoppar över roten summerar du det bästa värdet för varje barn. Detta är en postorder-DFS med ett ta-eller-hoppa-över-beslut vid varje nod.
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)) # 7Komplexitet och diskussion i intervjun
Den linjära House Robber-lösningen körs på O(n)-tid och använder O(1) minnesutrymme med optimeringen till två variabler. Den cirkulära varianten körs också på O(n)-tid eftersom den anropar den linjära versionen två gånger. Trädvarianten körs på O(n)-tid och använder O(h) minnesutrymme, där h är trädets höjd. Ange alltid komplexiteten efter kodningen i en intervju och nämn minnesoptimeringen — det visar att du tänker längre än en första fungerande lösning.
# 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}')Snabbtest
Testa er förståelse av begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionens sammanfattning
I den här lektionen lärde ni er: ta-eller-hoppa-över-rekurrensen dp[i] = max(dp[i-1], nums[i] + dp[i-2]), att reducera utrymmesåtgången från O(n) till O(1) med två rullande variabler och att utvidga mönstret till cirkulära arrayer och binära träd. Härnäst utforskar vi problemen Maximum Subarray och Maximum Product Subarray med Kadane's algorithm.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”House Robber: rekurrens för ta eller hoppa över” gratis?
Ja – hela texten till ”House Robber: rekurrens för ta eller hoppa över” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”House Robber: rekurrens för ta eller hoppa över”?
Modellera beslutet att råna eller hoppa över som en DP-rekurrens, minska utrymmet till två variabler och utöka lösningen till cirkulära hus. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”House Robber: rekurrens för ta eller hoppa över”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- House Robber: rekurrens för ta eller hoppa över
- Delarray med maximal summa och maximal produkt
- Word Break och segmentering av strängar
- Decode Ways och räkning av vägar