Pythonで解く「House Robber」問題：動的計画法による最大強盗金額の求め方

問題の概要

ある町に、それぞれ異なる金額が保管されている家々があります。一人の泥棒が一晩でこれらの家からお金を奪おうと考えています。

しかし、この町にはセキュリティシステムが設置されており、同じ夜に隣接する2軒の家が荒らされると、自動的に警察に通報される仕組みになっています。

この制約のもとで、泥棒が奪える金額の最大値を求めるのが、この問題の目的です。

問題の例

配列が与えられ、インデックス i における A[i] は i 番目の家にある金額を表します。

例えば、次のような配列を考えてみましょう。

A = [2, 7, 10, 3, 1]

この場合、答えは 13 になります。1番目の家（2）、3番目の家（10）、5番目の家（1）を選ぶことで、合計13という最大金額を得られます。隣接する家を避けて選択している点に注目してください。

解法のアプローチ

この問題は動的計画法（DP）を使って効率的に解けます。各時点で「その家を襲うか、襲わないか」を判断し、それまでの最適解を記録しながら進めていきます。

手順は以下の通りです。

• prev1 = 0、prev2 = 0 として初期化する
• i を 0 から配列 A の長さまで繰り返す：
  • temp = prev1 を保存する
  • prev1 = max(prev2 + A[i], prev1) を更新する（現在の家を襲う場合と襲わない場合の大きい方）
  • prev2 = temp を更新する
• 最後に prev1 を返す

ここで prev1 は「直前の家までの最大金額」、prev2 は「2つ前の家までの最大金額」を表しています。これにより、O(n) の時間計算量・O(1) の空間計算量で問題を解くことができます。

実装例

以下にPythonでの実装例を示します。

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        prev2 = 0
        prev1 = 0
        for i in range(0, len(nums)):
            temp = prev1
            prev1 = max(prev2 + nums[i], prev1)
            prev2 = temp
        return prev1

ob1 = Solution()
print(ob1.rob([2, 7, 10, 3, 1]))

入力

nums = [2,7,10,3,1]

出力

13

まとめ

House Robber問題は、動的計画法の基礎を学ぶのに最適な古典的なアルゴリズム問題です。「直前の結果」と「2つ前の結果」だけを保持することで、メモリを節約しながら線形時間で最適解を導き出せる点がポイントです。LeetCodeなどの競技プログラミングサイトでも頻出のテーマなので、ぜひ理解を深めておきましょう。