486. 预测赢家
这题拿到首先想到的是贪心算法，也联想到华工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));
}
}