38~39-预测赢家-石子游戏-递归

题目链接

位数是奇数，先手不一定能够赢。{1,200,2}。

上面，先手拿的话，使用贪心算法局部最优也是无法赢得石子游戏的。先拿6对手拿3，无论拿哪个都是输。
找到每一步最优的分。

class Solution {
    public boolean stoneGame(int[] arr) {
        int sum = 0;
        for(int i : arr) {
            sum+=i;
        }
        int p1 = maxScore(arr, 0, arr.length-1);
        return p1>sum-p1;
    }
    // 递归超时。。。
    public int maxScore(int[] arr, int l, int r) {
        if(l == r) return arr[l];
        int sLeft = 0, rRight = 0;
        if(r-l == 1) {
            sLeft = arr[l];
            rRight = arr[r];
        }
        if(r-l >= 2) {
          //  sLeft = arr[l] + Math.min(maxScore(arr, l+2, r), maxScore(arr, l+1, r-1));
        //    rRight = arr[r] + Math.min(maxScore(arr, l+1, r-1), maxScore(arr, l, r-2));
            int temp = maxScore(arr, l+1, r-1);
            sLeft  = arr[l] + Math.min(maxScore(arr, l+2, r), temp);
            rRight = arr[r] + Math.min(temp, maxScore(arr, l, r-2));
        }
        return Math.max(sLeft, rRight);
    }
}