一、捡石头 292

思路就是：

谁面对4块石头的时候，谁就输
（因为每次就是1-3块石头，如果剩下4块石头，你怎么拿，我都能把剩下的拿走，所以你就要想尽办法让对面面对4块石头的倍数，

• 比如有10块石头，你想办法让对方面对4的倍数，10%4=2，也就是你先手拿走2块
• 比如有13块石头，你想办法让对方面对4的倍数，13%4=1，也就是你先手拿走1块

但是假如你面对了4的倍数，你铁定输，因为对方也是聪明人。

于是先手能不能赢，就看

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0 ;
    }
}

二、捡石头 Nim 游戏 II 1908

int  nums = [ 1, 5, 8, 6 ]

我和你进行捡石头游戏，假如有4堆石头，
第一堆有1个石头，
第二堆有5个石头，
第三堆有8个石头，
第四堆有6个石头，

每次只能从最前面或者最后面取1堆石头，能否保证先手一定能赢？

分析如下：

public static void main(String[] args) {
        int[] nums = {1, 5, 8, 6};
        int[] nums2 = {3, 9, 1, 2};
        int[] nums3 = {1, 1, 1, 1};
        int[] nums4 = {2, 5, 1, 3, 7, 8, 9, 11};

        int[] nums5 = {1000,0,10000,2,1};
        int[] nums6 = {10, 8, 20, 15, 3};
        int[] nums7 = {1, 1, 1, 10};

//        int[] nums0 = {5, 8, 6};
//        System.out.println(firstHandCanScore(nums0));

        System.out.println(firstHandCanScore(nums));
        System.out.println(firstHandCanScore(nums2));
        System.out.println(firstHandCanScore(nums3));
        System.out.println(firstHandCanScore(nums4));
        System.out.println(firstHandCanScore(nums5));
    }

    private static boolean firstHandCanScore(int[] nums) {
        WinScoreData winScoreData = process(nums, 0, nums.length - 1);
        System.out.println(winScoreData.winScore);
        return winScoreData.winScore > 0;
    }

    private static WinScoreData process(int[] nums, int fromIndex, int toIndex) {
        if (fromIndex == toIndex) {
            return new WinScoreData(nums, fromIndex, toIndex, nums[fromIndex]);
        }
        int startLeft = nums[fromIndex];
        WinScoreData chooseLeftWinScore = process(nums, fromIndex + 1, toIndex);
        int leftWinScore = startLeft - chooseLeftWinScore.winScore; // 选左边之后的赢面

        int startRight = nums[toIndex];
        WinScoreData chooseRightWinScore = process(nums, fromIndex, toIndex - 1);
        int rightWinScore = startRight - chooseRightWinScore.winScore; // 选右边之后的赢面


        int winScore = Math.max(leftWinScore, rightWinScore);
        return new WinScoreData(nums, fromIndex, toIndex, winScore);
    }

    @AllArgsConstructor
    public static class WinScoreData {
        private int[] nums;
        private int fromIndex;
        private int toIndex;
        private int winScore;
    }