石子游戏

问题

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 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 。

思路一

因为有偶数堆，假设1…2n，那么先手的人先取1，则对手只能取2或2n，先手的人接下来能取到3或2n-1，即先手的人能确保取完所有奇数堆，对手取完偶数堆。同理先手的人先取2n，也能保证取完偶数堆，对手取完奇数堆。所以奇数堆和偶数堆那个和大，先手的人就决定取哪个堆，必胜。
代码直接返回 true

思路二

能不能赢，我们考虑最终比对手多几颗石子，或者说，面对石子堆，我们先取会比对手先取多多少个。
比如A先按规则取了最左或最右其中一堆石子假设个数为n，那么他比对手多了多少呢？
那么剩下的石子堆对于对手B而言就是先取，假设剩下的石子堆取完B比他多了m，那么最终他比对手多了
n - m 个石子。
所以子问题就是对一堆石子先手的人比对手最终多几颗石子，如果这个值是负的，说明比对手少。
我们设函数 为 区间的石子堆先手的人最多赢得的石子数。
那么状态转移公式：

• ，基本情况，只有一堆时，先手拿完
• 

二维dp数组需要斜着遍历
代码

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

        let mut j;
        // 斜着遍历，offset是列相对行的偏移量
        for offset in 1..n {
            for i in 0..n{
                j = i + offset;
                if j == n {
                    break;
                }
                dp[i][j] = std::cmp::max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }

        dp[0][n-1] > 0
    }
}

这个思路理解后简单，代码也简单

思路三

也可以让dp[i][j]表示先手者(本题中亚历克斯）比后手者(本题中李)多拿的数量。当轮到亚历克斯拿时，他会让这个数量增大，轮到李时会让这个数量减小。因为最后一堆石子是李拿，所以应该初始为负值。
状态转移方程要分情况
见如下代码：

impl Solution {
    pub fn stone_game(piles: Vec<i32>) -> bool {
        let n = piles.len();
        let mut dp = vec![vec![0_i32;n];n];
        // 初始为负值
        for i in 0..n {
            dp[i][i] = piles[i] * -1;
        }

        let mut j;
        // 斜着遍历，offset是列相对行的偏移量
        for offset in 1..n {
            for i in 0..n{
                j = i + offset;
                if j == n {
                    break;
                }

                // 剩余偶数堆，轮到亚历克斯拿，取更大值
                if (i - j + 1) % 2 == 0 {
                    dp[i][j] = std::cmp::max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1]);
                } else {
                // 剩余奇数堆，轮到李拿，让值减小，取更小的值
                    dp[i][j] = std::cmp::min(-piles[i] + dp[i+1][j], -piles[j] + dp[i][j-1]);
                }
                //dp[i][j] = std::cmp::max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }

        println!("{}", dp[0][n-1]);

        dp[0][n-1] > 0
    }
}

其它思路：解决博弈问题的动态规划通用思路