一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1498|回复: 12
收起左侧

[Leetcode] 有人做过Guess Number Higher or Lower II吗

[复制链接] |试试Instant~ |关注本帖
ginevoinee 发表于 2016-7-20 00:26:18 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

此外,discussion中都是dp解法,基本上只给出dp的转移方程,而没写dp数组的定义是什么,看不出来他们为什么这样构造转移方程。这道题如果按照minimax算法思路解应该怎么做呢?也许弄懂minimax解法的话对于弄懂dp解法有帮助,毕竟hint里说因为minimax复杂度太高才转用dp做的。
mnmunknown 发表于 2016-7-20 04:53:42 | 显示全部楼层
本帖最后由 mnmunknown 于 2016-7-20 05:10 编辑

试着用 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.

如果以 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.         int twoMax = values[n - coins] + values[n - coins + 1]
  4.                      + Math.min(memoizedSearch(coins - 3, values, dp),
  5.                                 memoizedSearch(coins - 4, values, dp));

  6.         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.         int[] dp = new int[n + 1];
  11.         Arrays.fill(dp, -1);
  12.         dp[0] = 0;
  13.         dp[1] = values[n - 1];
  14.         dp[2] = values[n - 1] + values[n - 2];

  15.         int sum = 0;
  16.         for(int num : values){
  17.             sum += num;
  18.         }

  19.         return 2 * memoizedSearch(n, values, dp) > sum;
  20.     }

  21.     private int memoizedSearch(int coins, int[] values, int[] dp){
  22.         if(coins < 0) return 0;
  23.         if(dp[coins] != -1) return dp[coins];
  24.         int n = values.length;

  25.         int oneMax = values[n - coins] + Math.min(memoizedSearch(coins - 2, values, dp),
  26.                                                   memoizedSearch(coins - 3, values, dp));

  27.         int twoMax = values[n - coins] + values[n - coins + 1]
  28.                      + Math.min(memoizedSearch(coins - 3, values, dp),
  29.                                 memoizedSearch(coins - 4, values, dp));

  30.         dp[coins] = Math.max(oneMax, twoMax);
  31.         return dp[coins];
  32.     }
  33. }
复制代码
回复 支持 1 反对 0

使用道具 举报

iluvatar077 发表于 2016-7-20 00:53:27 | 显示全部楼层
lz你是不是……没看懂题?
回复 支持 反对

使用道具 举报

 楼主| ginevoinee 发表于 2016-7-20 01:08:07 | 显示全部楼层
本帖最后由 ginevoinee 于 2016-7-20 01:10 编辑
iluvatar077 发表于 2016-7-20 00:53
lz你是不是……没看懂题?

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

使用道具 举报

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

首先说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有帮助。
回复 支持 反对

使用道具 举报

 楼主| ginevoinee 发表于 2016-7-20 02:49:50 | 显示全部楼层
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:02 | 显示全部楼层
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是哪棵。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

 楼主| ginevoinee 发表于 2016-7-21 00:48:52 | 显示全部楼层
本帖最后由 ginevoinee 于 2016-7-21 00:49 编辑
mnmunknown 发表于 2016-7-20 03:39
还没有做这题,不过觉得这个思路很赞~ 看起来有点像那个 N 层大楼扔鸡蛋的问题,最优策略是选择正确的楼 ...

十分感谢!你给的代码,我还需要再理解理解。。我没听过N层大楼扔鸡蛋的问题,你能给个问题链接或具体描述吗?
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-7-21 01:25:27 | 显示全部楼层
ginevoinee 发表于 2016-7-21 00:48
十分感谢!你给的代码,我还需要再理解理解。。我没听过N层大楼扔鸡蛋的问题,你能给个问题链接或具体描 ...

https://www.zhihu.com/question/19690210?nr=1

目前最高票答案中的一句: 这时候答案很明显了: 为了使两子树中高度最大者尽量小, 我们的选择应当使两子树高度尽量接近. 最终希望的结果是, 整个二叉树尽量像一个满二叉树.
回复 支持 反对

使用道具 举报

donghaox 发表于 2016-7-29 15:54:22 | 显示全部楼层
mnmunknown 发表于 2016-7-20 04:53
试着用 MiniMax 做了一下,已 AC 代码如下:

这题按类型分的话可以划为博弈类 DP,类似的还有 Lintcode  ...

求加好友!
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-7-29 21:38:14 | 显示全部楼层

已加~ 字数字数字数
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 08:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表