Skip to content

预测赢家

题目

[486] 预测赢家

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化

递归

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var PredictTheWinner = function(nums) {
  const total = nums.reduce((acc, x) => acc += x, 0);
  return maxScore(nums, 0, nums.length -1) >= total / 2;
};

function maxScore(nums, l, r) {
  if (l === r) {
    return nums[l];
  }
  if (l === r - 1) {
    return nums[l] >  nums[r] ?  nums[l] : nums[r];
  }

  // 玩家2，取过数最大数之后的几种情况。
  const scoreLeft = nums[l] + Math.min(maxScore(nums, l + 2, r), maxScore(nums, l + 1, r - 1));
  const scoreRight = nums[r] + Math.min(maxScore(nums, l + 1, r - 1), maxScore(nums, l, r - 2));

  return scoreLeft > scoreRight ? scoreLeft : scoreRight;
}

动态规划