博弈型
博弈型
核心：换序
博弈为两方游戏
一方先下，在一定规则下依次出招
如果满足一定条件，则一方胜
先手：先出招的一方
出招后，先手换序，新的先手面对一个新的局面
博弈动态规划通常从第一步分析，而不是最后一步
因为局面越来越简单，石子数越来越少
两类目标
先手是否必赢
先手差值最大
先手价值最大，可以用额外状态记录的方式来得到，也可以用(maxDif+sum)/2
状态结合
坐标型/完全背包（的写法2或写法1）
Coins in a Line
后缀型
Coins in a Line II, 石子游戏 II
区间型
Coins in a Line III, 石子游戏
状压型
我能赢吗
部分问题可以用数学法推出当前是否必胜
Coins in a Line
每人轮流拿1或2个，取走最后石子赢，问先手是否必赢
两人轮流从n个硬币的头部取一个硬币或者两个硬币，取走最后一个硬币者胜，问先手是否必胜
状态：f[i]表示i个石子时先手必赢
转移：f[i]=!f[i-1]||!f[i-2]
边界：f[0]=false
可以滚动数组优化至O(1)
Coins in a Line II
两人轮流从数组的头部取一个数或者两个数，取最大和者胜，问先手是否必胜
状态：f[i]表示从i到末尾
转移：f[i]=max{sum(i,i+1)-f[i+1], sum(i,i+2)-f[i+2]}
Coins in a Line III
两人轮流从数组任意一头取数，取最大和者胜，问先手是否必胜
目标：数字和最大
博弈+区间dp
状态：f[i][j]表示表示区间[i,j]的最小得分差
转移：f[i][j]=max{a[i]-f[i+1][j],a[j]-f[i][j-1]}
石子游戏
移除 最左边的石头或最右边的石头，并获得与石头值的得分。当没有石头可移除时，得分较高者获胜。
lc877.
状态：f[i][j]表示区间[i,j]的最大得分差
转移：f[i][j]=max{v[i]-f[i+1][j],v[j]-f[i][j-1]}
边界：f[i][i]=0
答案：f[0][n-1]>0
石子游戏 II
移除 最左边的石头或最右边的石头，并获得与石头值的得分。当没有石头可移除时，得分较高者获胜。返回先手可以得到的最大数量的石头
这个题很少见，边不可逆，需要用定义一或者刷表法法
lc1140. 类似前序型的定义，后序型
状态：dp[i][j]表示剩余[i : len - 1]堆时，M = j的情况下，先取的人能获得的最多石子数
转移：f[i][j]=max{sum(i,i+x-1)-f[i+x][max{x,m}]}
边界：f[i][i]=0
答案：min{f[n][j]}
石子游戏 III
比II简单多，每次只能从头拿1-3个
状态：f[i]表示，还剩下第i-n-1堆石子时，比下一位玩家多拿的数量
转移：f[i]=max{sum(i,j-1)-f[j]},j in [i+1,i+3]
答案：f[0]
顺序：i[n-1,0]
石子游戏 IV
每人轮流拿平方数个，取走最后石子赢，问先手是否必赢
状态：f[i]表示i个石子时先手必赢
转移：f[i]=or{!f[i-k]}
边界：f[0]=false
可以滚动数组优化至O(1)
石子游戏 VII
移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
lc1690.
状态：f[i][j]表示区间[i,j]的最小得分差
转移：f[i][j]=max{sum(i+1,j)-f[i+1][j],sum(i,j-1)-f[i][j-1]}
边界：f[i][i]=0
答案：f[0][n-1]
石子游戏 VIII
每人轮流拿平方数个，取走最后石子赢，问先手是否必赢
状态：f[i]表示剩余[i : n - 1]堆时，分数之差最大值
转移：f[i]=max{f[i+1], sum(0,i)-f[i+1]}
边界：f[n - 1]=sum(0,n-1)
可以滚动数组优化至O(1)
我能赢吗？
可以取任何一个位置的元素，需要状压来标记