有人做过Guess Number Higher or Lower II吗

题目hint中建议看minimax，但是我没看出来这道题和minimax有什么关系？我的理解是minimax问题中的双方每步都在使自己利益最大化，而这道题当人A开始选了一个数之后只有另一个人B一直在使自己利益最大化，而人A只是辅助功能（即，告诉人B猜高还是猜低），人A没有自己的利益。第一次接触这种博弈类问题，不太明白，有人能解释一下吗？

此外，discussion中都是dp解法，基本上只给出dp的转移方程，而没写dp数组的定义是什么，看不出来他们为什么这样构造转移方程。这道题如果按照minimax算法思路解应该怎么做呢？也许弄懂minimax解法的话对于弄懂dp解法有帮助，毕竟hint里说因为minimax复杂度太高才转用dp做的。

试着用 MiniMax 做了一下，已 AC 代码如下：

这题按类型分的话可以划为博弈类 DP，类似的还有 Lintcode 上的 Coins in a Line 1,2,3

我们先定义 dp[j]，代表着如果我们在区间 [i , j] 内进行查找，所需要的最少 cost 来保证找到结果。(当然，因为给定数字是 [1, n]，这里有一个 index off by one 的问题)。不难发现对于最开始的函数输入 n ，我们的最终结果就是 dp[0][n - 1] ，也即数字区间 [1 , n] 保证得到结果所需要的最小 cost.

[i]如果以 top-down recursion 的方式分析这个问题，可以发现对于区间 [i, j] ，我们的猜测  i <= k <= j 我们可能出现以下三种结果：
       1. k 就是答案，此时子问题的额外 cost = 0 ，当前位置总 cost  = k + 0;
       2. k 过大，此时我们的有效区间缩小为 [i , k - 1] 当前操作总 cost  = k + dp[start][k - 1];
       3. k 过小，此时我们的有效区间缩小为 [k + 1 , j] 当前操作总 cost  = k + dp[k + 1][j];

由于我们需要 “保证得到结果”，也就是说对于指定 k 的选择，我们需要准备最坏情况 cost 是以下三种结果生成的 subproblem 中cost 最大的那个； 然而同时对于一个指定区间 [i , j] ，我们可以选择任意 i <= k <= j ，对于这个 k 的主观选择可以由我们自行决定，我们要选的是 k  s.t. 其子问题的 cost + 当前操作 cost 最小的一个，至此，每次决策就构成了一次 MiniMax 的博弈。

同时因为我们有很多的 overlapping subproblems ，而且问题本身具有 optimal substructure，提高算法效率最简单直观的方式，就是用 int[][] dp 做缓存，来进行自顶向下的记忆化搜索 ( top-down memoized search).

1. public class Solution {
   
2.     public int getMoneyAmount(int n) {
   
3.         // dp[i][j] min cost to guarantee to win from interval [i , j]
   
4.         return getMinCost(0, n - 1, new int[n][n]);
   
5.     }
   
6.    
   
7.     private int getMinCost(int start, int end, int[][] dp){
   
8.         if(start >= end) return 0;
   
9.         
   
10.         if(dp[start][end] != 0) return dp[start][end];
    
11.         
    
12.         int minCost = Integer.MAX_VALUE;
    
13.         
    
14.         for(int i = start; i < end; i++){
    
15.             minCost = Math.min(minCost,  (i + 1) + Math.max(getMinCost(start, i - 1, dp),
    
16.                                                             getMinCost(i + 1, end, dp)));
    
17.         }
    
18.         
    
19.         dp[start][end] = minCost;
    
20.         
    
21.         return dp[start][end];
    
22.     }
    
23. }

复制代码

为了进行这类算法的比较，也附上自己写的 Coins in a line II 的 MiniMax 代码，可以看到核心的地方就是这里：

1. <i>       </i> int oneMax = values[n - coins] + Math.min(memoizedSearch(coins - 2, values, dp),
   
2.                                                   memoizedSearch(coins - 3, values, dp));
   
3. 
   
4.         int twoMax = values[n - coins] + values[n - coins + 1]
   
5.                      + Math.min(memoizedSearch(coins - 3, values, dp),
   
6.                                 memoizedSearch(coins - 4, values, dp));
   
7. 
   
8.         dp[coins] = Math.max(oneMax, twoMax);

复制代码

代表着在每一步上我有两个选择：拿一个硬币，拿两个硬币； 然而同时对手也有两个选择， 拿一个硬币，或者拿两个硬币。那么对于还有 n 个硬币剩余的情况下，我当前决策所能获得的最大收益就是 max ( 当前拿硬币的收益 + min(对手拿一个硬币留给我的最大收益，对手拿两个硬币留给我的最大收益) )

可以看到这题的 MiniMax 思路完全一致，只不过每一步的选择上变成了 [i , j] 区间内的个数，而不仅仅是 2 个，同时我们试图在最外围取 min cost ，而不是硬币问题中的 max profit.

1. public class Solution {
   
2.     /**
   
3.      * @param values: an array of integers
   
4.      * @return: a boolean which equals to true if the first player will win
   
5.      */
   
6.     public boolean firstWillWin(int[] values) {
   
7.         // write your code here
   
8.         int n = values.length;
   
9.         if(n <= 2) return true;
   
10. 
    
11.         int[] dp = new int[n + 1];
    
12.         Arrays.fill(dp, -1);
    
13.         dp[0] = 0;
    
14.         dp[1] = values[n - 1];
    
15.         dp[2] = values[n - 1] + values[n - 2];
    
16. 
    
17.         int sum = 0;
    
18.         for(int num : values){
    
19.             sum += num;
    
20.         }
    
21. 
    
22.         return 2 * memoizedSearch(n, values, dp) > sum;
    
23.     }
    
24. 
    
25.     private int memoizedSearch(int coins, int[] values, int[] dp){
    
26.         if(coins < 0) return 0;
    
27.         if(dp[coins] != -1) return dp[coins];
    
28.         int n = values.length;
    
29. 
    
30.         int oneMax = values[n - coins] + Math.min(memoizedSearch(coins - 2, values, dp),
    
31.                                                   memoizedSearch(coins - 3, values, dp));
    
32. 
    
33.         int twoMax = values[n - coins] + values[n - coins + 1]
    
34.                      + Math.min(memoizedSearch(coins - 3, values, dp),
    
35.                                 memoizedSearch(coins - 4, values, dp));
    
36. 
    
37.         dp[coins] = Math.max(oneMax, twoMax);
    
38.         return dp[coins];
    
39.     }
    
40. }

复制代码

ginevoinee 发表于 2016-7-20 02:49
谢谢你的解答。

我对你说的“策略”还是不太理解，为什么你说策略和target无关？我觉得是有关的，比如 ...

策略不是指一个数字序列，因为数字序列没有利用A的回答排除掉一些范围。虽然策略本身不依赖于target，但因为策略也考虑A的response，所以策略产生的结果（也就是每次猜什么数）当然是和target有关的。

对这个题合理的策略对应一棵1-n的BST，每个node是一次猜测，根结点对应B第一次猜测的数。然后根据A的回答可以排除掉当前node一侧的所有数，所以如果回答<就向左走，>就向右走，跟在BST里搜target是一样的。

所以换个表述，可以认为这个题是问，所有存了1-n的BST里，最大路径和最小的的BST是哪棵。

这个题其实和博弈没什么关系。感觉跟气球那个题更像。

首先说minmax:
对猜数字的人来说，猜测可以有不同的策略（比如顺序猜、二分等等），这个策略跟target是几没有关系。但对每个策略，根据target不同可能产生不同的代价。
minmax里的max是指给定一个策略，需要考虑最坏情况。例如假设你的策略是顺序猜，应该考虑要猜的数是n的可能性。min是指在所有可能的策略中，取最坏情况最小的一种作为最优策略。
所以你要求的是min_{所有策略} （max_{所有target} 这个策略和这个target所产生的代价）

然后说dp:
把要猜的数的范围从1-n推广到p-q。那么对每个pair (p, q)，都有一个minmax cost，假设这个是一个函数C(p, q)。这就是我们要计算的dp数组。
很显然地如果p>=q，也就是范围里只有0-1个数，则不产生代价。
当p<q时，假设第一次猜的是x，则可以根据target所在范围分三种情况，按照问题定义各自产生不同的代价。这里我们还是求minmax：给定x，我们需要考虑所有target的最坏情况，在最外层需要考虑所有x的取值，选其中代价最小的一个（最优策略）。

希望对lz有帮助。

lz你是不是……没看懂题？

iluvatar077 发表于 2016-7-20 00:53
lz你是不是……没看懂题？

我觉得看懂了吧。我理解的是题目要求求一个最小值k，使得无论人A从[1,n]中挑任何一个数，人B总能找出一种方案猜中，并且这种方案的总开销最多是k dollars。没错吧？

hxtang 发表于 2016-7-20 01:43
这个题其实和博弈没什么关系。感觉跟气球那个题更像。

首先说minmax:

谢谢你的解答。

我对你说的“策略”还是不太理解，为什么你说策略和target无关？我觉得是有关的，比如说人B在[1,3]范围内猜，如果按你说的策略和target无关，那么人B可以在人A选数之前就制定好一个策略，假如说是先猜2，再猜3，最后猜1。这样的话，如果人A选target=1的话，尽管事实上人B猜大了，理论上他下次应该猜1，但是根据事先定好的策略，人B下次猜的是3。

hxtang 发表于 2016-7-20 03:23
策略不是指一个数字序列，因为数字序列没有利用A的回答排除掉一些范围。虽然策略本身不依赖于target，但 ...

还没有做这题，不过觉得这个思路很赞~ 看起来有点像那个 N 层大楼扔鸡蛋的问题，最优策略是选择正确的楼层，使得我们得到的 BST 决策树层数最小？

mnmunknown 发表于 2016-7-20 03:39
还没有做这题，不过觉得这个思路很赞~ 看起来有点像那个 N 层大楼扔鸡蛋的问题，最优策略是选择正确的楼 ...

是的，但是扔鸡蛋那个题有约束条件（最多摔碎m个蛋）。所以决策树所有路径向左brach不能超过m次，这个会导致大量剪枝。但总之做法也是dp/memorized recursion。

mnmunknown 发表于 2016-7-20 03:39
还没有做这题，不过觉得这个思路很赞~ 看起来有点像那个 N 层大楼扔鸡蛋的问题，最优策略是选择正确的楼 ...

十分感谢！你给的代码，我还需要再理解理解。。我没听过N层大楼扔鸡蛋的问题，你能给个问题链接或具体描述吗？