C++で全ての本を購入するための最小コストを求める方法

問題の概要

n個の要素からなる配列があるとします。各要素は本の評価（レーティング）を表しています。以下の条件を満たすように、すべての本を購入する際の最小コストを求めます。

• 各本のコストは最低でも1ドル以上でなければならない
• ある本の評価が隣接する本（左または右）の評価より高い場合、その本のコストは隣の本よりも高く設定しなければならない

例えば、評価の配列が [1, 3, 4, 3, 7, 1] の場合、出力は 10 になります。これは 1 + 2 + 3 + 1 + 2 + 1 = 10 となるためです。

解法の考え方

この問題を効率的に解くには、LtoR と RtoL という2つの補助配列を用意し、すべての要素を1で初期化します。その後、次の手順で処理を進めます。

• 配列を左から右へ走査して LtoR を埋めます。直前の要素の評価と比較して値を更新しますが、次の要素の評価は考慮しません。
• 配列を右から左へ走査して RtoL を埋めます。こちらも直前（右隣）の要素の評価と比較して更新し、それ以外は考慮しません。
• 最後に、各位置 i における LtoR[i] と RtoL[i] の最大値を求め、それを結果に加算していきます。

この方法により、左右両方向の制約を同時に満たす最小のコストの組み合わせを構成できます。

C++での実装例

#include<iostream>
using namespace std;
int getMinCost(int ratings[], int n) {
    int res = 0;
    int LtoR[n];
    int RtoL[n];
    for(int i = 0; i < n; i++){
        LtoR[i] = RtoL[i] = 1;
    }
    for (int i = 1; i < n; i++)
        if (ratings[i] > ratings[i - 1])
            LtoR[i] = LtoR[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--)
        if (ratings[i] > ratings[i + 1])
            RtoL[i] = RtoL[i + 1] + 1;
    for (int i = 0; i < n; i++)
        res += max(LtoR[i], RtoL[i]);
    return res;
}
int main() {
    int ratings[] = { 1, 6, 8, 3, 4, 1, 5, 7 };
    int n = sizeof(ratings) / sizeof(ratings[0]);
    cout << "Minimum cost is: " << getMinCost(ratings, n);
}

出力結果

Minimum cost is: 15

動作の確認

入力配列 {1, 6, 8, 3, 4, 1, 5, 7} の場合、各配列は次のようになります。

• LtoR = [1, 2, 3, 1, 2, 1, 2, 3]
• RtoL = [1, 1, 2, 1, 2, 1, 1, 1]

各位置における最大値を合計すると、1 + 2 + 3 + 1 + 2 + 1 + 2 + 3 = 15 となり、これが最小コストとなります。

計算量

• 時間計算量：O(n) — 配列を3回走査するだけで済みます
• 空間計算量：O(n) — 2つの補助配列が必要です