2. Linux.do
  3. Leetcode每日一题 —— 486. 预测赢家

Leetcode每日一题 —— 486. 预测赢家

魔法师 2026-08-01 09:38 1


思路


看题目要么从左取要么从右取，第一时间想到DFS。

因为每个玩家都要用最优策略，所以两者都要计算当前情况下所能取到的最优。

这样会有很多重复计算，为了增加效率，我们把计算过的内部最优结果存起来。


补充说明



  1. DPS计算当前情况下，当前玩家能取得的最优差值结果。

  2. 之前的操作对剩余部分的最优结果没有任何影响，所以可以存到Hash里。（所以好像可以用这个规则写DP？）


代码


class Solution {

    private HashMap<Integer, Integer> vis;

    public boolean predictTheWinner(int[] nums) {

        vis = new HashMap<>();

        int res = dps(nums, 0, nums.length - 1, true, 0);

        return res >= 0;

    }



    private int dps(int[] nums, int l, int r, boolean first, int flag) {

        if (l == r) {

            return first ? nums[l] : -nums[l];

        }

        int left, right;

        int lFlag = flag + (1 << l), rFlag = flag + (1 << r);

        if (vis.containsKey(lFlag)) {

            left = vis.get(lFlag);

        } else {

            left = dps(nums, l + 1, r, !first, lFlag);

            vis.put(lFlag, left);

        }

        left += (first ? nums[l] : -nums[l]);

        if (vis.containsKey(rFlag)) {

            right = vis.get(rFlag);

        } else {

            right = dps(nums, l, r - 1, !first, rFlag);

            vis.put(rFlag, right);

        }

        right += (first ? nums[r] : -nums[r]);

        return first ? Math.max(left, right) : -Math.max(-left, -right);

    }

}
最新回复 (3)
  • Lvvvv 08-01 10:21
    1楼

    蛮力（


    class Solution {
    
public:
    
    bool predictTheWinner(vector<int>& nums) {
    
        int n = nums.size();
    
        auto choose = [&](this auto&& choose, int lp, int rp, int sum0, int sum1, bool player) -> bool {
    
            if(lp > rp) {
    
                return sum0 >= sum1;
    
            }
    
            if(!player) {
    
                return choose(lp + 1, rp, sum0 + nums[lp], sum1, !player) | choose(lp, rp - 1, sum0 + nums[rp], sum1, !player);
    
            } else {
    
                return choose(lp + 1, rp, sum0, sum1 + nums[lp], !player) & choose(lp, rp - 1, sum0, sum1 + nums[rp], !player);
    
            }
    
        };
    
        return choose(0, n - 1, 0, 0, 0);
    
    }
    
};
  • SomeBottle 08-01 10:22
    2楼

    递归解决，注意 dfs 是站在玩家 1 视角的。


    class Solution {
    
public:
    
    bool predictTheWinner(vector<int>& nums) {
    
        // 二者的选择是相互关联的，应该可以动态规划，也可以回溯
    
        auto dfs=[&](auto&& self,int l,int r,int sum1,int sum2,bool current)->bool{
    
            // 根据 current 知道当前轮到 1 (true) 还是 2 (false)
    
            // [l, r] 是这个玩家目前能操作的 nums 范围
    
            if(l>r){
    
                // 递归终点
    
                return sum1>=sum2;
    
            }
    
            if(current){
    
                // 目前是玩家 1，两个分支有一个能赢就行
    
                return self(self,l+1,r,sum1+nums[l],sum2,!current) ||
    
                self(self,l,r-1,sum1+nums[r],sum2,!current);
    
            }else{
    
                // 是玩家 2
    
                // 注意这里是 AND
    
                // 玩家 2 会采用最优策略阻挠玩家 1
    
                // 因此玩家 1 在玩家 2 两个分支下都能赢才算赢
    
                return self(self,l+1,r,sum1,sum2+nums[l],!current) &&
    
                self(self,l,r-1,sum1,sum2+nums[r],!current);
    
            }
    
        };
    
        return dfs(dfs,0,nums.size()-1,0,0,true);
    
    }
    
};
  • 欧拉线 08-01 13:01
    3楼 
    // dp[i] 表示当前玩家在区间 nums[i..j] 上能取得的净胜分（相对对手）
    
// 转移：取左端 nums[i] - dp[i+1]，取右端 nums[j] - dp[i]，取较大者
    
// 时间 O(n^2)，空间 O(n)
    
bool predictTheWinner(int* nums, int numsSize) {
    
    int dp[22] = {0}, len, i;
    
    for (len = 1; len <= numsSize; len++) {
    
        for (i = 0; i + len <= numsSize; i++) {
    
            int j = i + len - 1;
    
            int l = nums[i] - (len > 1 ? dp[i + 1] : 0);
    
            int r = nums[j] - (len > 1 ? dp[i] : 0);
    
            dp[i] = l > r ? l : r;
    
        }
    
    }
    
    return dp[0] >= 0; // 净胜分非负则玩家1赢（平局也算赢）
    
}
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐