C++で解く「石を1つの山にまとめる最小コスト」問題

問題概要

一列に並んだ N 個の石の山があり、i 番目の山には stones[i] 個の石が入っています。1 回の操作では、連続する K 個の山を 1 つの山にまとめることができ、このときのコストはその K 個の山に含まれる石の総数に等しくなります。

この問題では、すべての山を 1 つの山にまとめるための最小コストを求めます。なお、そもそも 1 つの山にまとめることが不可能な場合は -1 を返します。

具体例で確認

例えば、入力が [3, 2, 4, 1]、K = 2 の場合、出力は 20 になります。手順は以下の通りです。

• 初期状態：[3, 2, 4, 1]
• [3, 2] をコスト 5 でマージ → [5, 4, 1]
• [4, 1] をコスト 5 でマージ → [5, 5]
• [5, 5] をコスト 10 でマージ → [10]

合計コストは 5 + 5 + 10 = 20 となり、これが最小値となります。

解法のアプローチ

この問題は区間 DP（動的計画法）と累積和を組み合わせて解きます。手順は以下の通りです。

1. n を配列 stones のサイズとします。
2. (n - 1) % (k - 1) が 0 でない場合は -1 を返します。これは、毎回 K 個ずつ減らして最終的に 1 つにできるかどうかの判定条件です。
3. サイズ n + 1 の累積和配列 prefix を用意します。
4. i = 1 から n まで、prefix[i] = prefix[i - 1] + stones[i - 1] を計算します。
5. サイズ n × n の 2 次元配列 dp を定義します。dp[i][j] は「i 番目から j 番目までの山をまとめる最小コスト」を表します。
6. 区間の長さ length を k から n まで伸ばしながら、以下を繰り返します。
   • i = 0、j = length - 1 から始めて、j < n の間、i と j を 1 ずつ増やします。
   • dp[i][j] を INT_MAX で初期化します。
   • 分割位置 mid を i から j 未満まで k - 1 ずつ進めながら、dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]) で更新します。
   • 区間 (j - i) が (k - 1) で割り切れる場合（つまりこの区間を 1 つの山にまとめられる場合）、dp[i][j] += prefix[j + 1] - prefix[i] として区間全体の石の数を加算します。
7. 最後に dp[0][n - 1] を返します。

C++による実装例

以下の実装を見ると理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int mergeStones(vector<int>& stones, int k){
        int n = stones.size();
        if ((n - 1) % (k - 1) != 0)
            return -1;
        vector<int> prefix(n + 1);
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + stones[i - 1];
        }
        vector<vector<int>> dp(n, vector<int>(n));
        for (int length = k; length <= n; length++) {
            for (int i = 0, j = length - 1; j < n; i++, j++) {
                dp[i][j] = INT_MAX;
                for (int mid = i; mid < j; mid += k - 1) {
                    dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
                }
                if ((j - i) % (k - 1) == 0) {
                    dp[i][j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0][n - 1];
    }
};
main(){
    Solution ob;
    vector<int> v = {3,2,4,1};
    cout << (ob.mergeStones(v, 2));
}

入力

{3,2,4,1}, 2

出力

20