C++で解く「家からの最大窃盗価値」問題：動的計画法による効率的な解法

この問題では、n軒の家があり、それぞれの家には何らかの価値が保管されています。私たちの課題は、家々から盗むことができる最大の価値を見つけることです。

問題の説明

houses[] という配列には、各家に保管されている価値が格納されています。泥棒はこれらの家を次々と襲いますが、隣人が盗難に気づいてしまうため、隣り合う2軒から連続して盗むことはできません。この制約の中で、泥棒が捕まらずに盗むことのできる最大の合計価値を求める必要があります。

具体例で問題を理解しましょう。

入力

houses[] = {5, 2, 1, 6, 7, 9, 4, 3}

出力

23

説明

5、6、9、3 の家を選ぶことで、最大の価値 23 が得られます。

解法のアプローチ

この問題は動的計画法（DP）を使って効率的に解くことができます。泥棒があるインデックス i の家から盗んだ場合、インデックス (i+1) の家からは盗めず、同様にインデックス (i-1) の家も盗んでいないことになります。

この問題を解くために、サイズ n の DP 配列を作成します。まずベースケースとして、DP[0] に houses[0] を、DP[1] には houses[0] と houses[1] の大きい方を設定します。その後、インデックス 2 から n-1 までの DP の値を順番に求めていきます。DP[i] の値は、次の漸化式で表されます。

DP[i] = max(DP[i-2] + houses[i], DP[i-1])

つまり、「i 番目の家を盗む場合（直前の家はスキップ）」と「i 番目の家を盗まない場合」のうち、価値が大きい方を選びます。最終的に、DP 配列の最後の要素が盗むことのできる最大の価値となります。

この解法の動作を示すプログラム：

例

#include <iostream>
using namespace std;
int calMax(int a, int b){
    if(a > b)
        return a;
    return b;
}
int findMaxValuesStolen(int houses[], int n) {
    if (n == 0)
        return 0;
    int DP[n];
    DP[0] = houses[0];
    DP[1] = calMax(houses[0], houses[1]);
    for (int i = 2; i<n; i++)
        DP[i] = calMax( (houses[i] + DP[i-2]), DP[i-1]);
    return DP[n-1];
}
int main() {
    int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
    int n = sizeof(houses)/sizeof(houses[0]);
    cout<<"The maximum possible values stolen from the houses is "
    <<findMaxValuesStolen(houses, n);
    return 0;
}

出力

The maximum possible values stolen from the houses is 23

空間計算量を改善した最適化解法

上記の解法でも十分に機能しますが、さらに効率化できます。注目すべきは、DP の各ステップで参照しているのは直前の2つの値だけだという点です。そこで、DP 配列全体の代わりに変数を2つだけ使えば、同じ結果を得ることができます。これにより、空間計算量を O(n) から O(1) に削減できます。

最適化された解法の動作を示すプログラム：

例

#include <iostream>
using namespace std;
int calMax(int a, int b){
    if(a > b)
        return a;
    return b;
}
int findMaxValuesStolen(int houses[], int n) {
    if (n == 0)
        return 0;
    int maxValStolen;
    int val1 = houses[0];
    int val2 = calMax(houses[0], houses[1]);
    for (int i = 2; i<n; i++) {
        maxValStolen = calMax( (houses[i]+val1) , val2);
        val1 = val2;
        val2 = maxValStolen;
    }
    return maxValStolen;
}
int main() {
    int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
    int n = sizeof(houses)/sizeof(houses[0]);
    cout<<"The maximum possible values stolen from the houses is "<<findMaxValuesStolen(houses, n);
    return 0;
}

出力

The maximum possible values stolen from the houses is 23

計算量のまとめ

時間計算量： どちらの解法も配列を一度だけ走査するため、O(n) です。
空間計算量： DP 配列を使用する基本解法は O(n)、変数2つのみを使用する最適化解法は O(1) です。