leetcode-877-石子游戏

[博客链接]

一个菜🐔的学习之路

掘金首页

[题目描述]

  1. 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。 
  3.  游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。 
  5.  亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
  8.  假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。 
  12.  示例： 
  15. 输入：[5,3,4,5]
  16. 输出：true
  17. 解释：
  18. 亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
  19. 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
  20. 如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
  21. 如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
  22. 这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。
  27.  提示： 
  30.  2 <= piles.length <= 500 
  31.  piles.length 是偶数。 
  32.  1 <= piles[i] <= 500 
  33.  sum(piles) 是奇数。 
  35.  Related Topics 极小化极大 数学 动态规划 
  36.  👍 277 👎 0

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：数学-博弈论

  • 偶数长度数组先手情况总能拿到首尾两端相对较大的元素，所以一定先手赢
  1. public boolean stoneGame(int[] piles) {
  2.             return true;
  3.         }

时间复杂度O(1)

思路二：动态规划

  • 可以先考虑一个子问题就是在当元素数组只有两个元素的时候先手取Math.max(piles[0],pilse[1])
  • 递归向外同时扩展两侧区间[0, j + 1]
  • 无论先手后手取得一定是当前区间端点最大值可以扩大区间范围
  • 使用l, r分别代表左右边界如果先手取[l,r]内区间端点元素取左边元素时
  • 先手元素为piles[l-1],后手选取元素为Max[piles[l+1],piles[r]]取右边元素是
  • 先手元素为piles[r-1],后手选取元素为Max[piles[l],piles[r-1]]
  • 先手会优先考虑取得最大差值的情况我们假设a为先手元素，b 为后手元素
  • 也就是说我们先手取得的是Math.max[(a1-b1),(a2-b2)]
  • a1a2 b1b2 分别代表先手取左右两边元素得分和对应后手的得分情况如果按照递归思路的话可以简单定义一个递归函数int(int l, int r,int[] piles)
  • 表示在当前l,r为边界的时候取得的得分最大差值观察到可变参数为l,r
  • 所以可以定义一个dp[n+1][n+1]
  • n为piles数组长度 表示在左右边界为ij的情况下，先手取得的最大值与后手取得的差值最大值，保证每次先手得分最高
  • dp[i][j] = Math.max(a, b)
  1.  public boolean stoneGame(int[] piles) {
  2.             int n = piles.length;
  3.             int[][] dp = new int[n + 1][n + 1];
  4.             //
  5.             for (int i = 0; i < n; i++) {
  6.                 for (int j = i + 1; j < n; j++) {
  7.                     int a = piles[i] - dp[i + 1][j];
  8.                     int b = piles[j] - dp[i][j - 1];
  9.                     dp[i][j] = Math.max(a,b);
  10.                 }
  11.             }
  12.             return dp[0][n-1] > 0;
  13.         }

时间复杂度O(n^2)