LeetCode Guess Number Higher or Lower II 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 the first 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?

---

猜数字升级版。假设正确数字在[1,n]之间，每猜一个x，如果没猜中，则需要花费x元。问最少需要花费多少钱才能保证一定能猜中数字。 这是一个minmax问题，即最小化最大花费。使用动态规划解决，假设dp[l][r]表示在区间[l,r]猜数字时，一定能猜中的最小花费钱数。 假设在区间[l,r]猜数字，当猜x错误时，可以根据大小关系继续在[l,x-1]或[x+1,r]区间继续猜。假设已经知道[l,x-1]和[x+1,r]区间猜中的最小花费是dp[l][x-1]和dp[x+1][r]，则猜x猜中的最小花费就是f(x)=x+max(dp[l][x-1],dp[x+1][r])。x在[l,r]遍历，取最小的f(x)就是区间[l,r]猜中的最小花费。 代码如下： [cpp] class Solution { private: int helper(vector<vector<int>>& dp, int l, int r) { if (l >= r)return 0; if (dp[l][r] != 0)return dp[l][r]; dp[l][r] = INT_MAX; for (int k = l; k <= r; ++k) { dp[l][r] = min(dp[l][r], k + max(helper(dp, l, k – 1), helper(dp, k + 1, r))); } return dp[l][r]; } public: int getMoneyAmount(int n) { vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); return helper(dp, 1, n); } }; [/cpp] 本代码提交AC，用时59MS。 还可以用迭代的思路。DP的思路就是在一个大的区间[l,r]，尝试猜任意一个数x，然后取x+max(dp[l][x-1],dp[x+1][r])。但前提是小区间dp[l][x-1]和dp[x+1][r]之前已经算过了。 所以可以令l=n-1→1，r=l+1→n，x在[l,r)任意取值，因为x是从x-1遍历到x的，所以dp[l][x-1]算过了；又因为l是从n-1,n-2,..,x+1,x,x-1,…遍历的，所以dp[x+1][r]也是算过了，这样就能求f(x)=x+max(dp[l][x-1],dp[x+1][r])。 为什么不能令l=1→n-1，r=l+1→n呢，假设此时选择x，则虽然算过dp[l][x-1]，但没算过dp[x+1][r]，因为左端点的遍历顺序是1,2,…,l,…,x-1,x,x+1,…，左端点只遍历到l，还没遍历到x+1，所以dp[x+1][r]的值还没算好。 迭代的代码如下： [cpp] class Solution { public: int getMoneyAmount(int n) { vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); for (int l = n – 1; l > 0; –l) { for (int r = l + 1; r <= n; ++r) { dp[l][r] = INT_MAX; for (int k = l; k < r; ++k) { dp[l][r] = min(dp[l][r], k + max(dp[l][k – 1], dp[k + 1][r])); } } } return dp[1][n]; } }; [/cpp] 本代码提交AC，用时9MS，快了好多。]]>