阿祁的部落格

LeetCode 877 - Stone Game 解題心得( 題目 )

解題概念:數學邏輯

解題方法:一開始會以為是DP，雖然DP也會過，但會發現自己的時間怎麼輸給其他人那麼多...。直到發現驚為天人的解法。

我們觀察陣列是個2的倍數的陣列，既然這樣如果我是先手，我的目標就是從奇數位數和偶數位數選一個比較大的，然後盡可能全部拿走，如果是奇數的，我一開始就拿奇數那邊(最左邊是奇數、最右邊則是偶數)，那這樣另一人拿的兩邊都是偶數位，因為他得選一邊，所以再來輪到你又會有一邊奇數一邊偶數，重複以下流程，你最後一定可以拿到全部的奇數，所以答案其實一定是True!所以最後發現前面那些都可以不用考慮，先手一定會贏!

Java參考程式碼(有更好意見可留言於下方，謝謝!)

class Solution {

    public boolean stoneGame(int[] piles) {

        return true;

    }

}