C++で解く数当てゲームII（Guess Number Higher or Lower II）：最小支払額を求める動的計画法

問題概要

数当てゲーム（Guess Game）を考えてみましょう。ゲームのルールは次の通りです。

• プレイヤー1が1からnまでの整数の中から1つの数字を選びます。プレイヤー2は、その数字を当てる役割です。
• プレイヤー2の予想が外れるたびに、プレイヤー1は「選んだ数字はもっと大きい」か「もっと小さい」かを教えてくれます。

ただし、プレイヤー2がある数字xを予想して外れた場合には、xドルを支払わなければなりません。プレイヤー2が正解した時点でゲームは終了です。

この問題の目的は、相手がどの数字を選んでいても必ず当てられるようにするための最小の支払額を求めることです。

具体例

n = 10、プレイヤー1が選んだ数字が8の場合を考えます。

• 1回目：プレイヤー2が「5」と予想 → 外れ。実際はもっと大きいため、5ドル支払う。
• 2回目：プレイヤー2が「7」と予想 → 外れ。実際はもっと大きいため、7ドル支払う。
• 3回目：プレイヤー2が「9」と予想 → 外れ。実際はもっと小さいため、9ドル支払う。

これで残る候補は8だけとなり、ゲーム終了です。合計支払額は 5 + 7 + 9 = 21ドル となります。

解法のアプローチ

この問題は、自分の予想（min）と相手の最悪の対応（max）を交互に考える、いわゆるミニマックス戦略の発想で解きます。さらに区間ごとの結果をキャッシュするメモ化再帰（動的計画法）を組み合わせることで、効率よく答えを導けます。

手順は以下の通りです。

• cost(low, high, dp) というメソッドを作成します。
• low >= high の場合は 0 を返します（候補が1つ以下なら追加コストは不要）。
• dp[low][high] が -1 以外なら、その値を返します（メモ化済みのため再計算しない）。
• ans を無限大（INT_MAX）で初期化します。
• i を low から high まで動かしながら、ans = min(ans, i + max(cost(low, i−1, dp), cost(i+1, high, dp))) を更新します。
• dp[low][high] に ans を保存して返します。

メインの処理では、(n+1) × (n+1) の2次元配列 dp を作成して -1 で初期化し、cost(1, n, dp) の結果を返します。

ポイントは、各区間の分割位置 i について「左側 cost(low, i−1)」と「右側 cost(i+1, high)」のうち大きい方（最悪ケース）を採用し、その中で最小になる i を選ぶ点です。相手がこちらにとって最も不利な状況を作ろうとすることを想定しているためです。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int cost(int low, int high, vector<vector<int>>& dp){
        if(low >= high) return 0;
        if(dp[low][high] != -1) return dp[low][high];
        int ans = INT_MAX;
        for(int i = low; i <= high; i++){
            ans = min(ans, i + max(cost(low, i - 1, dp), cost(i + 1, high, dp)));
        }
        return dp[low][high] = ans;
    }
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
        return cost(1, n, dp);
    }
};
int main() {
    Solution ob1;
    cout << ob1.getMoneyAmount(8) << endl;
    return 0;
}

入力

8

出力

12

n = 8 の場合、どの数字を選ばれても確実に勝つために必要な最小金額は 12ドル であることが分かります。

なお、このアルゴリズムの時間計算量は O(n³)、空間計算量は O(n²) です。区間の組み合わせが O(n²)、それぞれについて分割位置の探索に O(n) かかるためです。メモ化により同じ区間の再計算が省かれるため、全探索に比べて大幅に高速化されています。