LeetCode每日一题-2021-06-15-877. 石子游戏-486. 预测赢家

LeetCode每日一题-2021-06-15-877. 石子游戏-486. 预测赢家
博弈论问题,衡为true,我猜的

如果是偶数确实先手必赢,现在考虑更为普适的奇偶都有的情况

这类题型为区间DP或者双人博弈

  1. 状态与子问题
    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的时候初始化过了

上一篇:成功解决AttributeError : ‘GridSearchCV‘ object has no attribute ‘grid_scores_‘


下一篇:bootstrap