博客

877. 石子游戏
     
     Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

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

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

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。


思路


写这道题的初衷就是，为什么有人的题解写的那么难懂还特么好意思。写不明白就不要写好嘛。

直接思考的话，但凡是先手，都会赢啊。但是总要写一些结构化的代码来证明吧。

直接切到dp，写状态转移方程。（其实还不太懂啥时候用dp。先会用再说吧。一步步来

dp[i][j] 代表 先手 比 后手 大多少

这里有个数组，左端点i 右端点 j

1.拿左边的i的话，就是arr[i] – dp[i + 1][j] 右边就是 j – 1.

取Max

2.状态转移方程有了就要琢磨怎么 让他遍历起来

目标 就是 dp[i][n-1] 是否 大于0.

先找base。总要有base。全未知的话还搞啥

只有一堆石头的时候。不论从左边还是右边 差值都是石子数。先到先得哎

画个图的话。就是对角线有值了。下面部分无意义，忽略。求右上角。

根据状态转移方程，i，j由 左边和下边决定。所以从下向上遍历即可

代码

 public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0;i < n;i++) {
            dp[i][i] = piles[i];
        }
        for (int i = n - 1;i >=0;i--) {
            for (int j = i + 1;j < n;j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j-1]);
            }
        }
        return dp[0][n-1] > 0;
    }