486. 预测赢家

有推文说这个东西
https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486013&idx=2&sn=ad0211c2b25a1ac1ce10aa5bd95298ae&chksm=fa0e65bccd79ecaa62958b412f9281c3540feaacbd9b907909d9c1042019c452f2d879402a6f&mpshare=1&scene=1&srcid=&sharer_sharetime=1564892422151&sharer_shareid=7cbf78ab6aa95ea110b6be75ecd8f18b&key=9a1722142ec4caad9274b361e8dd155be4c9e893ae1aeedaf119f2a19737863e5b6509bc540ff7a7bac9acbb14fa2c3d64d2e9101594d392c4ff9e41ea28eee8685b0aee9f7dc4be1772a7cb8385a61a&ascene=1&uin=MTgzNDAwNTI3OQ%3D%3D&devicetype=Windows+10&version=62060833&lang=zh_CN&pass_ticket=GM7MNvlPlkBBVKP6NMe7QC3h4uWkISHJBg0%2FuZnvPyTyF2buLHvZcBD37jApXAtd
{{uploading-image-473377.png(uploading...)}}

这题拿到首先想到的是贪心算法，也联想到华工ACM那道管子题，想每次都拿最大的，但是好像不行，有些情况明显不适用，比如{1,5,233,7}这个测试用例，对于这种情况，若贪心算，则会先拿7，但是拿7的话，233就会被后手拿了。所以并不可行。
emmm。然后想到了递归

每个玩家都要自己成绩最好所以不能当方面考虑一方
https://www.bilibili.com/video/av31317000?from=search&seid=5864670697835878797
递归的思路为：先双头取递归到底层然后再返回回来，而双头取的策略就是选择一个数自己不是亏很多的也就是有下面的 y-1 x+1

//选取评价函数为先手得分-后手得分，博弈树有重叠的部分可以重复利用。
//对面也是同样的策略
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return getSorce(0, nums.length-1, nums) >= 0;
    }
    public int getSorce(int x, int y, int nums[]) {
        if (x == y)
            return nums[x];
        else {
            return Math.max(nums[x] - getSorce(x + 1, y, nums), nums[y] - getSorce(x, y - 1, nums)); //先递归下去 然后再返回值上来 什么6-4 5-5 7-3
        }
    }
}

递归有相同子问题一般可以转化为动态规划

class Solution {
    public boolean PredictTheWinner(int[] nums) {
         int n=nums.length;
        int [][]dps=new int[n][n];
        //dps[i][i]为玩家一从i到i赢得，肯定只能是nums【i】
        for(int i=0;i<n;i++)
            dps[i][i]=nums[i];
        //d=1,其实代表，先算两个数的时候
        for(int d=1;d<n;d++)
        {
            //有多少组要比较
            for(int j=0;j<n-d;j++)
            {
                //比较j到d+j
                //其实意思就是比较j到d+j时，玩家1，只能选择两端的，
                //玩家一选择了j时，那么玩家二就从j+1到d+j中选最大的。
                //玩家一选了d+j时，那么玩家二就从j到d+j-1中选最大的
                dps[j][d+j]=Math.max(nums[j]-dps[j+1][d+j],nums[d+j]-dps[j][d+j-1]);
                System.out.println("dps["+j+"]["+(d+j)+"]=Math.max(nums["+j+"]-dps["+(j+1)+"]["+(d+j)+"],nums["+(d+j)+"]-dps["+j+"]["+(d+j-1)+"])");
            } 
        }
        for(int i = 0 ; i < dps.length;i++) {
            for(int x = 0 ; x < dps[i].length;x++) {
                System.out.print(dps[i][x]+" ");
            }System.out.println();
        }
        //两个玩家相等，玩家一仍然胜利。
        return dps[0][n-1]>=0;
    }
}
public class Main{
    public static void main(String[] args) {
        Solution s = new Solution ();
        int [] p = new int [] {1,3,3,2,5};
        System.out.println(s.PredictTheWinner(p));
    }
}