House Robber：取るかスキップするかの漸化式
rob/skipの選択をDPの漸化式としてモデル化し、空間を2つの変数に削減して、円環状に並ぶ家へ解法を拡張します。
「House Robber：取るかスキップするかの漸化式」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
House Robber問題
House Robber問題では、各家にある金額を表す非負整数の配列が与えられ、隣り合う2軒の家を同時に盗むことなく盗める金額の最大値を求めます。たとえば、[2, 7, 9, 3, 1]の場合は12になります（家0、2、4を選びます）。これは各ステップで二者択一の判断を行う、典型的な1D DP問題です。
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漸化式の定義
dp[i]を、最初のi+1軒の家から盗める金額の最大値とします。各家 i では、2つの選択肢があります。その家を飛ばす（dp[i-1]を取る）か、その家から盗む（nums[i] + dp[i-2]を取る）かです。漸化式はdp[i] = max(dp[i-1], nums[i] + dp[i-2])です。これは、多くの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])) # 12DP表をたどる
[2, 7, 9, 3, 1]について表をたどってみましょう。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です。最終的な答えはdp[4] = 12です。表を手作業でたどると、各位置で選択とスキップの両方を漸化式が正しく処理していることを確認できます。
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)に削減する
DP表は常に2つ前の位置までしか参照しないため、配列全体を2つの変数に置き換えられます。prev2（2つ前の値）とprev1（1つ前の値）です。各反復の後で、prev2 = prev1、prev1 = currentのように値をずらします。これにより、時間計算量をO(n)に保ったまま、メモリ使用量をO(n)から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処理すべきエッジケース
必ずエッジケースで解をテストしてください。空の配列（0を返す）、要素が1つの配列（その要素を返す）、要素が2つの配列（2つの最大値を返す）などです。面接でこれらのケースに言及し、処理できることを示すと、丁寧に考えていることが伝わります。if n == 1のガードにより、dp[1]のためにnums[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：円形に並んだ家
円形版（LeetCode 213）では家が円状に並ぶため、最初の家と最後の家が隣り合っています。線形の漸化式をそのまま適用することはできません。重要な考え方は、最初の家を盗んで最後の家を除外するか、最初の家を除外して最後の家を含めるかのどちらかだということです。2つの部分配列それぞれに線形のHouse Robberを適用し、最大値を取ります。
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ここで貪欲法が失敗する理由
単純な貪欲法では、常に利用可能な中で最も金額の大きい家を盗もうとするかもしれません。しかし、[2, 1, 1, 2]のような入力では失敗します。貪欲法では家0（値2）を選び、次に家3（値2）を選ぶため、合計は4です。一方、家0と家2を盗んでも3になります。待ってください—この場合は貪欲法でも正しく動作します。しかし、[1, 3, 1, 3, 100]を試してみましょう。貪欲法では3と3（インデックス1と3）を選んで6になりますが、最適解である1+1+100=102を逃してしまいます。局所的に最適な選択が、全体の最適解を保証するとは限らないため、DPが必要です。
# 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選択またはスキップパターンの見抜き方
選択またはスキップパターンは、House Robber以外にも一般化できます。配列を走査し、各位置で現在の要素を含める（直前の要素をスキップする）か、現在の要素を除外する（直前までの結果を維持する）かを選ぶ場合は、選択またはスキップDPです。隣り合う2つの要素を選べない、重複する区間を選べないといった制約があれば、このパターンを適用する手がかりになります。
# 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-likeDelete and Earnの変種
Delete and Earn（LeetCode 740）では、選んだ各数値についてnum × count(num)を得ますが、num-1とnum+1の出現をすべて削除しなければなりません。これはHouse Robberに直接帰着できます。すべての値についてearn[v] = v × count(v)となる配列を作り、その配列にHouse Robberを適用します。このような帰着を見抜く力は、面接で重要なスキルです。
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：二分木
House Robber IIIでは、家が二分木として配置されています。あるノードとその直接の親を同時に盗むことはできません。2つの値を返すヘルパーを定義します。rob(node) → (rob_root, skip_root)です。ルートを盗む場合は、左右の子のスキップ値を合計します。ルートをスキップする場合は、それぞれの子について最善の値を合計します。これは各ノードで選択またはスキップの判断を行うポストオーダーDFSです。
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計算量と面接での説明
線形のHouse Robberは、2変数による最適化を使うとO(n)時間、O(1)空間で実行できます。円形版も線形版を2回呼び出すだけなので、O(n)時間で実行できます。木構造版はO(n)時間、O(h)空間で実行できます。ここで h は木の高さです。面接では、コーディング後に必ず計算量を述べ、空間最適化にも言及してください。最初に動く解を作るだけでなく、その先まで考えていることを示せます。
# 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}')クイックチェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、取るかスキップする漸化式 dp[i] = max(dp[i-1], nums[i] + dp[i-2])、2つのローリング変数で空間計算量を O(n) から O(1) に削減する方法、このパターンを円形配列と二分木に拡張する方法を学びました。次は、Kadane法を使って最大部分配列問題と最大積部分配列問題を扱います。
よくある質問
「House Robber：取るかスキップするかの漸化式」レッスンは無料ですか？
はい。「House Robber：取るかスキップするかの漸化式」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「House Robber：取るかスキップするかの漸化式」で何を学びますか？
rob/skipの選択をDPの漸化式としてモデル化し、空間を2つの変数に削減して、円環状に並ぶ家へ解法を拡張します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「House Robber：取るかスキップするかの漸化式」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- House Robber：取るかスキップするかの漸化式
- 最大部分配列と最大積部分配列
- Word Breakと文字列の分割
- Decode Waysと経路のカウント