《算法问题实战策略》——chaper9——动态规划法技巧

时间:2021-08-02 06:20:52

Q1:

数字游戏:

两个人(A、B)用n个整数排成的一排棋盘玩游戏,游戏从A开始,每个人有如下操作:

(1)    拿走棋盘最右侧或者最左侧的棋子,被拿走的数字从棋盘中抹掉。

(2)    棋盘中还剩下两个以上的数字的时候,可以把棋盘最右侧或者最左侧的两个数字抹掉

当棋盘上的所有数字消失之后,游戏结束,谁拿的棋子代表的整数之和较大谁赢,现在假设两个游戏者都是聪明的,给出长度为n的序列,请计算游戏结束之后A的分数和B的分数的差值。

分析:其实相似的问题在《训练指南》当中曾经分析过,那个题目叫做“sum游戏”,这种题型其实是基于动规的博弈题,和棋盘游戏用到最多的极小化极大算法其实是本质相同的。

那么回到这个问题上来,我们看到它是基于一个一维的整数序列,那么不管它是博弈还是什么,我们都可以用线性dp的方法将其子问题化。

设dp[left][right]表示面临区间[left,right]的玩家的得分和剩下的那个玩家得分的差值,那么我们会得到如下的状态转移方程式(用board[]储存n个整数的序列):

《算法问题实战策略》——chaper9——动态规划法技巧

最终答案即dp[1][n].