【C++】3つの連続する要素ごとに1つ選ぶ場合の最小合計を求めるアルゴリズム

n個の要素からなる配列が与えられたとき、配列内の3つの連続する要素ごとに少なくとも1つの要素を選ぶという条件を満たしながら、選んだ要素の合計を最小化する問題を考えてみましょう。

問題の例

例えば、配列が [1, 2, 3, 6, 7, 1] の場合、出力は 4 になります。これは「3」と「1」を選ぶことで 3 + 1 = 4 が達成できるからです。

このとき、配列には次のような連続する3要素の部分配列が存在します。

• [1, 2, 3]
• [2, 3, 6]
• [3, 6, 7]
• [6, 7, 1]

これらすべての部分配列から1つずつ要素を選ぶ必要があるため、単純に小さい要素だけを選ぶわけにはいきません。

解法のアプローチ:動的計画法

sum(i) を「arr[i] を解の一部として選び、かつそれが最後に選んだ要素である場合の最小合計」と定義します。このとき、最終的な答えは sum(n-1)、sum(n-2)、sum(n-3) の中の最小値となります。

この問題には重複する部分問題が含まれているため、動的計画法(DP)を用いることで効率的に解くことができます。遷移式は以下の通りです。

sum[i] = arr[i] + min(sum[i-1], sum[i-2], sum[i-3])

C++での実装例

#include <iostream>
using namespace std;

int minOfThree(int a, int b, int c) {
    return min(min(a, b), c);
}

int getMinSum(int arr[], int n) {
    int sum[n];
    sum[0] = arr[0];
    sum[1] = arr[1];
    sum[2] = arr[2];
    for (int i = 3; i < n; i++)
        sum[i] = arr[i] + minOfThree(sum[i-3], sum[i-2], sum[i-1]);
    return minOfThree(sum[n-1], sum[n-2], sum[n-3]);
}

int main() {
    int arr[] = {1, 2, 3, 20, 2, 10, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum sum is: " << getMinSum(arr, n);
}

実行結果

Minimum sum is: 4

計算量

このアルゴリズムは配列を一度走査するだけなので、時間計算量は O(n)、補助配列 sum[] を使用するため空間計算量も O(n) となります。直近3つの値のみを保持すれば空間を O(1) に削減することも可能です。