LeetCode877. Stone Game

1、题目链接

https://leetcode-cn.com/problems/stone-game/

2、解题思路

这道题意思是有一排偶数的石子堆，每堆石子上都有一些正整数的石子，这些石子的总数是一个奇数，有两个人亚历克斯和李每次都从这堆石子的最前面和最后面取石子（一堆一堆取），亚历克斯先取，如果最后亚历克斯手中的石子多余李的，返回true，否则返回false，一开始我就想不管怎么样先取的总是赢的，因为两个人足够聪明，而且是从两边开始取，我先取的可以先计算出怎么样取对我最有利，这道题的关键就是先取和从两头取，所以不管怎么计算，最终总是返回true的，但是我们今天要用dp的思想来计算，我们用一个数组来保存两者的石子差值，用dp[i] 表示第i天两个人手里的石子差（亚历克斯和李的差值），那么就有dp[i] = Math(最左，最右) + (dp[i-1] - Math(最左，最右))，怎么理解呢，第i天亚历克斯可以取左右两边的大值，再加上（前一天的差值 减去 李取的那个小值）就是当天的差值了，最后返回dp[n/2]是否大于0就好了

3、代码

public static boolean stoneGame(int[] piles) {
    int[] dp = new int[piles.length / 2 + 1];
    dp[0] = 0;
    int right = piles.length - 1;
    for (int left = 1; left < piles.length / 2 + 1; left++) {
        dp[left] = Math.max(piles[left - 1], piles[right]) + dp[left - 1] - Math.min(piles[left - 1], piles[right]);
        right--;
    }
    return dp[piles.length / 2] > 0;
}

4、结果

WX20190828-194748@2x.png