[LeetCode] 375. Guess Number Higher or Lower II

[grandyang]

 

We are playing the Guess Game. The game is as follows: 

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

 

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Hint:

1. The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in thefirst scenario.
2. Take a small example (n = 3). What do you end up paying in the worst case?
3. Check out this article if you're still stuck.
4. The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
5. As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?

Credits:
Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.

 

此题是之前那道 Guess Number Higher or Lower 的拓展，难度增加了不少，根据题目中的提示，这道题需要用到 Minimax 极小化极大算法，关于这个算法可以参见这篇讲解，并且题目中还说明了要用 DP 来做，需要建立一个二维的 dp 数组，其中 dp[i][j] 表示从数字i到j之间猜中任意一个数字最少需要花费的钱数，那么需要遍历每一段区间 [j, i]，维护一个全局最小值 global_min 变量，然后遍历该区间中的每一个数字，计算局部最大值 local_max = k + max(dp[j][k - 1], dp[k + 1][i])，这个正好是将该区间在每一个位置都分为两段，然后取当前位置的花费加上左右两段中较大的花费之和为局部最大值，为啥要取两者之间的较大值呢，因为要 cover 所有的情况，就得取最坏的情况。然后更新全局最小值，最后在更新 dp[j][i] 的时候看j和i是否是相邻的，相邻的话赋为j，否则赋为 global_min。这里为啥又要取较小值呢，因为 dp 数组是求的 [j, i] 范围中的最低 cost，比如只有两个数字1和2，那么肯定是猜1的 cost 低，是不有点晕，没关系，博主继续来绕你。如果只有一个数字，那么不用猜，cost 为0。如果有两个数字，比如1和2，猜1，即使不对，cost 也比猜2要低。如果有三个数字 1，2，3，那么就先猜2，根据对方的反馈，就可以确定正确的数字，所以 cost 最低为2。如果有四个数字 1，2，3，4，那么情况就有点复杂了，策略是用k来遍历所有的数字，然后再根据k分成的左右两个区间，取其中的较大 cost 加上k。

当k为1时，左区间为空，所以 cost 为0，而右区间 2，3，4，根据之前的分析应该取3，所以整个 cost 就是 1+3=4。

当k为2时，左区间为1，cost 为0，右区间为 3，4，cost 为3，整个 cost 就是 2+3=5。

当k为3时，左区间为 1，2，cost 为1，右区间为4，cost 为0，整个 cost 就是 3+1=4。

当k为4时，左区间 1，2，3，cost 为2，右区间为空，cost 为0，整个 cost 就是 4+2=6。

综上k的所有情况，此时应该取整体 cost 最小的，即4，为最后的答案，这就是极小化极大算法，参见代码如下：

 

解法一：

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for (int i = 2; i <= n; ++i) {
            for (int j = i - 1; j > 0; --j) {
                int global_min = INT_MAX;
                for (int k = j + 1; k < i; ++k) {
                    int local_max = k + max(dp[j][k - 1], dp[k + 1][i]);
                    global_min = min(global_min, local_max);
                }
                dp[j][i] = j + 1 == i ? j : global_min;
            }
        }
        return dp[1][n];
    }
};

 

下面这种是递归解法，建立了记忆数组 memo，减少了重复计算，提高了运行效率，核心思想跟上面的解法相同，参见代码如下：

 

解法二：

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> memo(n + 1, vector<int>(n + 1, 0));
        return helper(1, n, memo);
    }
    int helper(int start, int end, vector<vector<int>>& memo) {
        if (start >= end) return 0;
        if (memo[start][end] > 0) return memo[start][end];
        int res = INT_MAX;
        for (int k = start; k <= end; ++k) {
            int t = k + max(helper(start, k - 1, memo), helper(k + 1, end, memo));
            res = min(res, t);
        }
        return memo[start][end] = res;
    }
};

 

Github 同步地址：

#375

 

类似题目：

Guess Number Higher or Lower

Flip Game II 

Can I Win 

Find K Closest Elements

 

参考资料：

https://leetcode.com/problems/guess-number-higher-or-lower-ii/

https://leetcode.com/problems/guess-number-higher-or-lower-ii/discuss/84787/Java-DP-solution

https://leetcode.com/problems/guess-number-higher-or-lower-ii/discuss/84764/Simple-DP-solution-with-explanation~~

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

没看出来2有什么好处， 在discussion里面看到张昆玮大神的solution， 好牛！！！
time complexity O(N^2), 自己看着算法写了一遍。
https://artofproblemsolving.com/community/c296841h1273742

class Solution {
public:
int getMoneyAmount(int n) {
vector<vector> f(n+1, vector(n+1,0));
for(int b = 2; b<=n; ++b){
int k0 = b-1;
deque dq;
for(int a = b-1; a>0; --a){
while(f[a][k0-1] > f[k0+1][b]) --k0;
while(!dq.empty() && dq.front() > k0) dq.pop_front();
int f2 = f[a][k0]+k0+1;
int vc = f[a+1][b]+a;
while(!dq.empty() && vc <= f[dq.back()+1][b]+dq.back()){
dq.pop_back();
}
dq.push_back(a);
int f1 = f[dq.front()+1][b] + dq.front();
f[a][b] = min(f1, f2);
}//a
}//b
return f[1][n];
}
};