lc375 猜数字大小2

A从1到n之间选择一个数字让B来猜，假设B猜数字x，如果猜对，直接结束；否则B需要支付金额x，然后A告诉B小了或者大了并继续猜。给定数字n，问能确保获胜的最小现金，无论A选择哪个数字。
1<=n<=200

区间dp，记dp[i][j]表示区间为[i,j]时获胜所需的最小现金，枚举每次猜的数字k，考虑最坏情况进行转移即可。注意，如果区间长度为1，肯定能猜中，花费为0，因此d从2开始枚举。

class Solution {
public:
    int dp[205][205];
    int getMoneyAmount(int n) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = 0;
            }
        }
        for (int d = 2; d <= n; d++) {
            for (int i = 1; i+d-1 <= n; i++) {
                int j = i+d-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];
    }
};