【C++】隣接する2つの要素を選ばない最大合計の求め方（動的計画法による解法）

この問題では、配列 arr[] が与えられます。「どの2つの要素も元の配列で隣り合わない」という条件を満たしながら要素を選んだとき、合計の最大値をC++で求めるプログラムを作成しましょう。

問題の概要

配列の中から要素を選んで合計を作る際、選んだ要素どうしが隣接してはいけないという制約があります。この条件下で実現できる合計の最大値を求めるのが目的です。

具体例を見てみましょう。

入力

arr[] = {5, 1, 3, 7, 9, 2, 5}

出力

22

説明

インデックス0から1つおきに要素を選んだ場合 : 5 + 3 + 9 + 5 = 22
インデックス1から1つおきに要素を選んだ場合 : 1 + 7 + 2 = 10

解法のアプローチ

前回の記事では単純な解法を紹介しましたが、今回は動的計画法（Dynamic Programming）を使ったより効率的な解法を学びます。

動的計画法で解くには、各インデックスまでの最大合計を記録しておくDP[]配列を作成します。そして、このキャッシュを参照しながら最適な合計を求めていきます。

インデックスiにおける最大値は、次の2つのうち大きい方になります。

• dp[i+2] + arr[i] … 現在の要素を選ぶ場合
• dp[i+1] … 現在の要素を選ばない場合

つまり「今の要素を取るか、取らないか」を各位置で比較し、結果をメモ化していくことで、同じ部分問題を何度も計算する無駄を省きます。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
    if(a > b)
        return a;
    return b;
}
int calcMaxSumWOAdj(int arr[], int i, int n){
    if (i >= n)
        return 0;
    if (currState[i])
        return DP[i];
    currState[i] = 1;
    DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
    return DP[i];
}
int main(){
    int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
    int n = sizeof(arr) / sizeof(int);
    cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
    return 0;
}

出力

The maximum sum such that no two elements are adjacent is 22

コードのポイント

• calcMaxSumWOAdj 関数は再帰的に呼び出され、インデックス i 以降で得られる最大合計を返します。
• currState 配列は「すでに計算済みかどうか」を示すフラグで、一度計算した結果は DP 配列にキャッシュされます（メモ化再帰）。
• この実装では計算量が O(n) になり、全パターンを調べる総当たり法（O(2^n)）に比べて大幅に高速です。