问一道题 coins in line II

dp[i] = values[i] + Math.min(dp[i+2],dp[i+3]);
dp[i] = Math.max(dp[i],values[i]+values[i+1]+ Math.min(dp[i+3],dp[i+4]));
状态转移方程大概是这样 我想问这里为什么要最小化选手1可以取得硬币的值 题目只是问选手1是赢还是输没有必要取最坏情况吧？
这里取max不行吗？让对手都选最少的 取最好的情况 看能不能赢

题目虽然没有明说, 但是问你"will XXX win"的题, 一般都暗含"双方都采取最优策略"这个假设, 否则这题就没什么意思了. 所以, 之所以状态转移方程要"最小化选手1可以在i以后取得硬币的值", 是因为选手2为了获胜一定会这么做, 因此状态转移方程必须模拟对手的这个策略.

stellari 发表于 2016-10-12 08:15
题目虽然没有明说, 但是问你"will XXX win"的题, 一般都暗含"双方都采取最优策略"这个假设, 否则这题就没什 ...

多谢大神 所以这种博弈论的题目都是要考虑自己可以选择的最差选择里面取最优？

33847682 发表于 2016-10-12 09:46
多谢大神 所以这种博弈论的题目都是要考虑自己可以选择的最差选择里面取最优？

这是一种可行的思路. 另外你也可以这样考虑: 令dp[ i ]为"到游戏结束为止, 在i处先拿的人比后拿的人能够多拿的面值".  如果i处先拿的人只拿1枚, 那么在i处他比对方多拿values[ i ], 但是在i+1~N处,对手可以比他多拿dp[ i+1 ], 也就是他比对手多拿-dp[ i + 1]. 因此从i到N, 他比对方多拿values[ i ]-dp[ i+1 ];同理, 如果先拿的人拿2枚, 那么能比对方多拿values[ i ] + values [ i + 1] - dp[ i + 2] .取这二者最大值即可得 dp [ i ], 最后看dp [ 0 ] 是大于还是小于 0 即可. 这样的话, 状态转移方程会比你说的那个解法要简单些, 而且也没有"最差选择"这种思维方式.

stellari 发表于 2016-10-12 12:47
这是一种可行的思路. 另外你也可以这样考虑: 令dp[ i ]为"到游戏结束为止, 在i处先拿的人比后拿的人能够 ...

明白了 那像这种minmax的题目都可以像你说的这种方法去考虑嘛？ 比如Guess Number Higher or Lower II这道题 用minmax是可以做出来的 用你的想法可以做嘛？