隣り合わない最大値 (House Robber)｜コードで実践

隣り合わない最大値 (House Robber)

このレッスンで分かること

DP は 必要な過去だけを覚える

実は dp 配列全体を保持する必要はなく、直前 2 つの値 だけ覚えておけば十分です

通称 House Robber 問題 とは、配列に「家ごとの現金」が並んでいて、隣り合う 2 軒を同時に襲うとアラームが鳴ってしまう、という設定です

隣り合わない最大値とは

隣り合う要素を同時に選べないという制約の下、配列から取り出せる最大合計を DP で求めます。本レッスンでは、隣り合わない最大値の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

通称 House Robber 問題 とは、配列に「家ごとの現金」が並んでいて、隣り合う 2 軒を同時に襲うとアラームが鳴ってしまう、という設定です。プレイヤーは 隣り合わないように家を選んで 合計金額を最大化したい、というシナリオです。例えば [2, 7, 9, 3, 1] なら、2 + 9 + 1 = 12 が最大です。7 + 3 = 10 よりも 12 の方が多いことに注意してください。

この問題は 「選ぶか / 選ばないか」 の二択を全要素について考える、典型的な動的計画法の入門です。LIS と違って大小の制約はなく、隣接制約だけがあります。

House Robber は 取捨選択型 DP の代表例。各ステップで「取る / 飛ばす」を選ぶ構造はナップサックや株売買にも通じる。

状態の定義

dp[i] を「i 番目までの家を見て得られる最大金額」とします。i 番目の家について、次の 2 通りを考えます。

取らない: dp[i] = dp[i - 1]
取る: dp[i] = dp[i - 2] + nums[i] (1 つ前は飛ばす必要がある)

両者の max を取って dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) です。

境界条件は dp[0] = nums[0]、dp[1] = max(nums[0], nums[1]) です。

図解

diagram (will load when visible)

図のポイント (テキスト併記)

どちらの遷移を選ぶかを 1 軒ずつ判断していくだけ、というシンプルな構造です

どちらの遷移を選ぶかを 1 軒ずつ判断していくだけ、というシンプルな構造です。

Python 実装 (配列版)

Python

def rob(nums):
    n = len(nums)
    if n == 0:
        return 0
    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], dp[i - 2] + nums[i])
    return dp[n - 1]

空間 O(1) に圧縮

実は dp 配列全体を保持する必要はなく、直前 2 つの値 だけ覚えておけば十分です。これにより空間計算量を O(1) に削減できます。

Python

def rob(nums):
    prev2 = 0
    prev1 = 0
    for num in nums:
        current = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = current
    return prev1

変数 2 つだけで進めるこの形が、面接などでもよく書かれる「上品な」回答です。prev1 が dp[i-1] に、prev2 が dp[i-2] に対応します。

JavaScript 実装

JavaScript

function rob(nums) {
  let prev2 = 0;
  let prev1 = 0;
  for (const num of nums) {
    const current = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

よくある間違い

1 つ目は 隣接制約を忘れて貪欲法 (greedy) で書く ケース。「大きい順に取って隣だけ飛ばす」では最適にならない反例が [2, 1, 1, 2] です。[2, 1, 1, 2] を例にすると、「大きい要素から順に取り、隣は飛ばす」貪欲では最初にインデックス0の 2 を選び、インデックス1をスキップ後にインデックス2の 1 を選んで合計 3 になります。しかし正解は両端の 2 + 2 = 4 であり、貪欲は最適解を逃しています。DP で必ず確認しましょう。2 つ目は 境界条件の場合分け忘れ。n == 0 や n == 1 を最初に処理しないと、dp[1] でクラッシュします。3 つ目は 空間 O(1) 版で更新順を間違える。prev2 = prev1 を prev1 = current より前に書く必要があります。

計算量

時間計算量は O(n)、空間計算量は配列版で O(n)、変数 2 つの圧縮版で O(1) です。動的計画法の中でもとくに無駄が少なく、入門としてうってつけです。「過去 2 つだけを覚える」というパターンはフィボナッチ数列の漸化式とそっくりで、感覚を共有しています。

DP は 必要な過去だけを覚える。配列全体を保持するか、変数 2 〜 3 つで済ませるかは状況次第。

やってみよう

[1, 2, 3, 1] の答えは 4 (1 + 3)。2 + 1 = 3 ではない。
円環版 (1 軒目と最後の軒も隣接) はどう解くか考えてみる。[0..n-2] と [1..n-1] の 2 回 DP するのが定石。
同じ問題を メモ化再帰 でも書いて、上の反復 DP と等価であることを確認する。
「どの家を盗んだか」のリストも返す版にする。dp[i] の遷移で「取った / 取らなかった」を別途記録すると復元できる。

House Robber は 「選ぶか / 選ばないか」 型 DP の基礎。空間 O(1) まで圧縮できる感覚が身につくと、他の DP 圧縮も楽になる。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は グリッド経路数 (Unique Paths) で、グリッドの左上から右下まで右または下にだけ進めるときの経路の総数を DP で数え上げる手法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

隣り合わない最大値の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 隣り合わない最大値とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

隣り合わない最大値 (House Robber)