Đoán số cao hơn thấp hơn II trong C++

Game đoán số 1..n. Mỗi lần đoán sai x phải trả $x. Tìm chi phí tối thiểu đảm bảo thắng trong trường hợp xấu nhất.

Ví dụ: n = 8 → 12.

Thuật toán giải quyết (DP khoảng - Minimax)

cost(low, high) = chi phí tối thiểu cho khoảng [low, high].

1. Nếu low >= high → 0.
2. Thử mọi i trong [low, high]: chi phí = i + max(cost(low, i-1), cost(i+1, high)).
3. Lấy min của các chi phí trên.
4. Memoization dp[low][high].

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
    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;
    }
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
        return cost(1, n, dp);
    }
};

int main() {
    Solution ob;
    cout << ob.getMoneyAmount(8);
}

Đầu vào

8

Đầu ra

12