(区间dp,minmax问题,极大极小)375. 猜数字大小 I

375. 猜数字大小 II

class Solution {
public:
    int getMoneyAmount(int n) {
        int dp[n + 2][n + 2];
        memset(dp, 0, sizeof dp);
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = 1e9;
                for (int k = i; k <= j; k++) {
                    dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j]));
                }
            }
        }
        return dp[1][n];
    }
};