C++で解く「House Robber II」：円状に並んだ家からの最大強奪額を動的計画法で求める

問題概要

あなたはプロの泥棒だとします。ある通りに沿って建ち並ぶ家々を襲う計画を立てており、各家にはそれぞれ一定額のお金が保管されています。ただし、家々は円状に配置されており、最初の家と最後の家も互いに隣接しています。

さらに、隣り合う家同士はセキュリティシステムで連結されており、同じ夜に隣接する2軒の家が泥棒に入ると自動的に警察へ通報される仕組みになっています。そこで、各家の保管金額を表す整数の配列が与えられたとき、警察に通報されずに一晩で奪える金額の最大値を求めるのがこの問題の目的です。

例えば、配列が [1,2,3,1] の場合、出力は 4 となります（1番目と3番目の家を選んで 1 + 3 = 4）。

解法のアプローチ

この問題は動的計画法（DP）を用いて解きます。円状という条件を扱う鍵は、問題を次の2つのパターンに分割することです。

• 最初の家を含み、最後の家を含まないケース
• 最後の家を含み、最初の家を含まないケース

それぞれのケースで線形版の「House Robber」問題として解き、両者の最大値を答えとします。

solve() 関数の処理手順

配列、開始インデックス start、終了インデックス end を受け取る solve() 関数を用意し、以下のように動作させます。

• ans := nums[start] で初期化する
• nums と同じサイズのDPテーブル dp を作成する
• dp[start] := nums[start] と設定する
• i を start + 1 から end まで繰り返す：
  • last := dp[i − 1]（直前の結果）
  • lastToLast := i − 2 が start 未満なら 0、そうでなければ dp[i − 2]
  • dp[i] := max(nums[i] + lastToLast, last)
  • ans := max(dp[i], ans)
• 最後に ans を返す

rob() 関数の処理手順

• n := nums のサイズ
• n が 0 の場合は 0 を返す
• n が 1 の場合は nums[0] を返す
• それ以外は max(solve(nums, 0, n − 2), solve(nums, 1, n − 1)) を返す

それでは、以下の実装を見ながら理解を深めましょう。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<int>& nums, int start, int end){
        int ans = nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        for(int i = start + 1; i <= end; i++){
            int last = dp[i - 1];
            int lastToLast = i - 2 < start ? 0 : dp[i - 2];
            dp[i] = max(nums[i] + lastToLast, last);
            ans = max(dp[i], ans);
        }
        return ans;
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(!n)return 0;
        if(n == 1)return nums[0];
        return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
    }
};
main(){
    vector<int> v = {1,2,3,5};
    Solution ob;
    cout << ob.rob(v);
}

入力

[1,2,3,5]

出力

7

この例では、2番目と4番目の家（金額 2 と 5）を選ぶことで、合計 7 という最大金額を達成できます。