博弈论问题,衡为true,我猜的
如果是偶数确实先手必赢,现在考虑更为普适的奇偶都有的情况
这类题型为区间DP或者双人博弈
-
状态与子问题
dp[i][j]
: 定义为两个玩家对弈,即先手后手对弈,对弈区间为scores[i:j]
,在区间上两个人的最大分数差(先手总分数-后手总分数),易判断i一定得小于等于j,等于的时候区间缩为一个点对于当前先手玩家,他只有两种选择,拿最左边的
scores[i]
或者最右边的socres[j]
∮当前先手玩家选择
scores[i]
,那么后手玩家只能在scores[i+1:j]
的两端选择,那么dp[i+1][j]
即为后手玩家在scores[i+1:j]
这个区间,比先手玩家多至多多少分,加个负号就变成这个区间上先手玩家比后手玩家的最大分差,因此先手玩家选左端点所得到的最大分差为scores[i] + ( - dp[i+1][j] )
∮同理当前先手玩家选择
scores[j]
,那么后手玩家只能在scores[i:j+1]
的两端选择,那么dp[i][j+1]
即为后手玩家在scores[i:j+1]
这个区间,比先手玩家多至多多少分,加个负号就变成这个区间上先手玩家比后手玩家的最大分差,因此先手玩家选右端点所得到的最大分差为scores[j] + ( - dp[i][j+1] )
综上所述,因为每个人发挥出最佳水平,所以最终的最大分差是上面两个分差取最大值
2.状态转移方程
dp[i][j] = Math.max( scores[i] + ( - dp[i+1][j] ) , scores[j] + ( - dp[i][j+1] ) );
3.初始值与边界值
当dp[i][i]时,区间只有一个店,谁拿谁赢,先拿先赢,即dp[i][i] = scores[i]
4.遍历顺序
不知道怎么遍历的时候可以画个图,状态是怎么转移过来的,表现在二维矩阵中,当前状态是由左边状态和下边状态转移而来的,因此i肯定是从n-1到0的,而要保证i衡小于j,则j应该从i+1到n-1,j=i的时候初始化过了