House Robber：取るかスキップするかの漸化式

House Robber問題

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 12

漸化式の定義

# 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]))  # 12

DP表をたどる

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])

空間をO(1)に削減する

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]))       # 4

処理すべきエッジケース

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]))    # 10

House Robber II：円形に並んだ家

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]))  # 4

ここで貪欲法が失敗する理由

# 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))  # 102

選択またはスキップパターンの見抜き方

# 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-like

Delete and Earnの変種

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：二分木

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))  # 7

計算量と面接での説明

# 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}')

クイックチェック

レッスンのまとめ