算法分析李xx抢公章案数据结构与算法weixin43936997的博客-

x总必胜无疑

理由是：从历史上看比”夺门之变”更惨烈的”玄武门”之变，最后的胜利者可是姓”李”。

不开玩笑的说，这事可以用算法来证明。

最优策略(Optimal Strategy)

这场”夺门之变”对看客来说是吃瓜大戏。
对“x总”和“夫人”来说也就是一场博弈游戏。
为了更好的说明这个问题，我们可以把“这个瓜”映射到下面的模型上。

1 x总和夫人交替发招 2 可以从{"水军":8 , “上诉”:15, “裁员”:3, "抢章":7 } 字典中选择动作(现实情况可选择的动作要比这个多很多)   每个动作都会给选择人带来收益。我们把收益抽出来组成【8, 15, 3, 7】列表。 3 每个参与者必须根据对手的策略做出选择，为了接近真实情况，我们加入如下限制：   只能从列表的头部或者尾部选择收益。 4 获胜条件：最后收益最大的人获胜。 

我们就用这个小规模问题来演示最优策略思路

x总在[8, 15, 3, 7]中选择7.
夫人在[8,15, 3] 中选择8.
x总在[15, 3]中选择15.
夫人最后只能选择3了.
x总最后的收益为： 22(7 + 15)

由于问题规模较小，这是我们用眼睛解题的过程。那如果规模较大呢？

辅助工具递归树

1. 我们定义函数os，它可以返回对应规模问题的最优解。
   本例中os(i=1, j=4) 代表问题规模为从1到4

2. 两个规模之间存在的关系为

os(i,j) = max(             val[i] + min( os(val, i+1, j-1), os(val, i+2, j)),             val[j] + min( os(val, i, j-2), os(val, i+1, j-1))             ) 

参加游戏的人都不是傻子，在做出本次选择后，你的对手一定会在剩下的方案中去寻找最优解，所以你下一次能拿到的值，一定是os(i+2, j), os(i+1, j-1)中小的那一个。

3. 退出条件
   I > J 此时全部问题处理完
   I == J 返回val[I]
   I == J+1 返回最后两个中的最大值。

有了思想，代码就不难了。

奉上代码

def os(val, i, j):     if i > j:         return          if i == j:         return val[i]          elif j == i + 1:         return max(val[i], val[j])     else:         return max(             val[i] + min( os(val, i+1, j-1), os(val, i+2, j)),             val[j] + min( os(val, i, j-2), os(val, i+1, j-1))             )       val = [8, 15, 3, 7] i = 0 j = len(val) res = os(val, i, j-1) opponent=sum(val) - res print("做为先手你可以拿到:{}n你的对手可以拿到:{}".format(res, opponent)) 

输出:

做为先手你可以拿到:22 你的对手可以拿到:11 

这段代码中，会有Overlapping Subproblems问题，优化一下为：

def os(val, i, j):     if i > j:         return     if dp[i][j] == -1:         if i == j:             dp[i][j] = val[i]         elif j == i + 1:             dp[i][j] = max(val[i], val[j])         else:             dp[i][j] = max(                 val[i] + min( os(val, i+1, j-1), os(val, i+2, j)),                 val[j] + min( os(val, i, j-2), os(val, i+1, j-1))                 )     return dp[i][j]  val = [8, 15, 3, 7] i = 0 j = len(val) dp = [[-1]*j for _ in range(j)] res = os(val, i, j-1) opponent=sum(val) - res print("做为先手你可以拿到:{}n你的对手可以拿到:{}".format(res, opponent)) 

对动态规划细节感兴趣，可以参考我以前的博文，链接我放到文章末尾。
用算法来观察这个世界是不是很有趣？！

先下手为强

像x总这样的老江湖，能力自然不言而喻。这次能够先出
手，发动雷霆一击，一定在背后把所有细节推演过无数遍。
通过我们刚才对最优策略学习，应该意识到：“这先下手的一方，只要不出现大失误，x总基本就赢定了。先下手就是强。”

你支持谁？

如果这是一场零和博弈，你只能在x总和夫人中选一个人，你会支持谁？
请写在评论区，让世界听见你的声音！

当然也欢迎你把更好的解决思路，写在评论区。

我的其他动态规划文章
最火的瓜，得用动态规划来吃
A姓女友，B姓女友，渣男与最长公共子串（有视频）
社区举办“杀戮游戏”，你能活下来吗？