题目

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

输入：[5,3,4,5]输出：true解释：亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。假设他取了前 5 颗，这一行就变成了 [3,4,5] 。如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

提示：

2 <= piles.length <= 500

piles.length 是偶数。

1 <= piles[i] <= 500

sum(piles) 是奇数。

思路分析

这道题有许多思路。

我们选择两个最能考验思想的给大家讲一讲。

解法1-数学分析

首先是一个取巧的想法。在这种你取一颗，我取一颗的过程中，极有可能出现一种情况。假设有偶数个数字：

[0,1,2,3,4,5,6,7]

可以看出，头是偶数，尾是奇数，而且穿插排列，那么对于在这种状态下先手的人来说，他有一种策略，他可以拿到所有奇数或者偶数位的数字。具体的操作情况见下：

假设A先手。A想拿到所有偶数，A可以先拿0，这样在B选择的时候只剩1和7，都是奇数，而在B拿完一边之后，会露出来一个偶数2或者6，在这种情况下，A将该偶数拿走，剩下给B的又全部是奇数。

按照这个顺序，A 如果想，一定能拿到所有的偶数，那么B就被迫拿了所有的奇数，同理，A也可以选择拿到所有的奇数，那么B就被迫拿了所有的偶数。

在这种条件下，如果所有偶数位的和与奇数位的和不同，那么A就有必胜策略 ，而题目中的条件告诉我们，偶数位的和与奇数位的和相加是一个奇数，所以必定有一个大，有一个小，那么A一定有必胜策略。

所以直接return true;就可以了

代码就懒得贴了。

解法2-动态规划

老方法，来个dp的模板

|递推公式|dp[i][j]=max(num[i]-dp[i+1][j],num[j]-dp[i][j-1])

–|

|边界条件|dp[i][i]=0,其余等于INT_MIN

|dp[i][j]的意义|边界范围包含[i,j]的子数组先手可以获得的最大分差

注意这个递推的时候不能按照常规的for (i…) for(j…)

会出错，因为我们的i，j不是按顺序递增的。

从递推公式可以看出，是一个典型的模拟过程，也就是说，如果有dp[i][j]，且A是先手，A有两个选择，一个是选头，一个是选尾。

选头的话，剩下的数组就是[i+1][j]，但此时对于B来说是先手，dp[i+1][j]的意义是B先手的情况下B可以获取的最大分差，所以我们应拿num[i]减去dp[i+1][j]，才能获取A获取的最大分差。

选尾部的情况同理。

C++代码

class Solution {
   public:    bool stoneGame(vector
   
    & piles) {
           int n = piles.size();        vector
    
     
      > dp(n, vector
      
       (n, INT_MIN));        for (int i = 0; i < n; ++i)            dp[i][i] = piles[i];        for (int len = 1; len < n; ++len)            for (int i = 0; i + len < n; ++i) {
                   int j = i + len;                dp[i][j]=max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1]);            }        return dp[0][n - 1] > 0;    }};

Rust代码

impl Solution {    pub fn stone_game(piles: Vec
   
    ) -> bool {        let n = piles.len();        let mut dp = vec![vec![i32::MIN; n]; n];        for i in 0..n {            dp[i][i] = piles[i];        }        for len in 1..n {            for i in 0..(n - len) {                let j = i + len;                dp[i][j] = (piles[i] - dp[i + 1][j]).max(piles[j] - dp[i][j - 1]);            }        }        dp[0][n - 1] > 0    }}

转载地址：http://juuci.baihongyu.com/

你可能感兴趣的文章