leetcode每日一题之486.预测赢家

发布时间:2021-02-12 发表于话题:预测赢家软件收费嘛 点击:11 当前位置:财神股票资讯网 > 游戏 > leetcode每日一题之486.预测赢家 手机阅读

理解dp的本质:

假设我是玩家1,对手是玩家2
每一个格子是我作为玩家,设身处地地假设我本人或者我的对手面对着区间[i,j],做出最好的选择后能领先的最高分数

当我面对着[i,j]这个区间的时候,我作为一个玩家选择i位置或者j位置,那么我的对手只能选择[i+1,j]格子内的分数,而如果我选择了j,我的对手只能选择[i,j-1]格子内的分数。
但是[i+1,j]和[i,j-1]内格子的分数如何计算呢?

敲黑板:

假如我选择了i,那么我的对手会领先[i+1,j]内的分数,而我新吸收了i位置的分数,所以我会比我的对手领先nums[i]-dp[i+1][j]假如我选择了j,那么我的对手会领先[i,j-1]格子内的分数,而我新吸收了j位置的分数,所以我会比我的对手领先nums[j]-dp[i][j-1]

注:dp(i,j)是dp表格中(i,j)位置的分数,即不论是我(玩家1)还是对手(玩家2)在这个格子作出选择后能领先的最多分数

完成整张表之后,我怎么知道我(玩家1)能不能在对手(玩家2)也作出最好的选择的情况下还是领先呢?
只要看DP(0,len(nums)-1)的位置里的领先分数是否>=0就可以了,因为在动态规划更新的过程中,每一个格子都是我为自己,或者为对手设身处地思考得到的最佳分数。
而我现在查看DP(0,len(nums)-1)这个位置,就代表我在这个位置是拥有选择权的。而我(玩家1)确实在这个位置有选择权,因为我是全局先手。

如何确立边界范围呢??
我们要得到最终dp[0][nums.size()-1]是否大于等于0,可以看出推导方程的时候一定要从右上角向下推导,而且矩阵的左半部分根本不用管。

class Solution { public: bool PredictTheWinner(vector& nums) { int length = nums.size(); auto dp = vector (length, vector(length)); for (int i = 0; i for (int j = i + 1; j public: bool PredictTheWinner(vector& nums) { int len=nums.size(); auto dp=vector (len); for(int i=0;i for(int j=i+1;j

本文来源:https://www.thyysj.com/info/267628.html

标签组:[dp

相关APP下载

热门话题

游戏推荐文章

游戏热门文章