一,问题描述

图片.png

二,暴力递归

2.1 分析

[1,2,100,4]为例.
A开始可以拿走1或者4
分情况
拿走1,情况为[2,100,4],这时B可以拿走2或者4,然后轮到A拿
拿走2,情况为[1,2,100],这时B可以拿走1或者100,然后轮到A拿

具体情况如下图 图片.png 先拿后拿交替进行
在举个例子 图片.png

2.2编码

两个过程交替进行,先拿和后拿也是交替进行,所以定义两个递归函数f(i,j)和s(i,j)

图片.png

public static int win1(int[] arr)
    {
        if(arr==null||arr.length==0)
        {
            return 0;
        }
        return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1));
    }
    public static int f(int[] arr,int i,int j)
    {
        //base case
        if(i==j)
        {
            return arr[i];
        }
        return Math.max(arr[i]+s(arr,i+1, j),arr[j]+s(arr, i, j-1) );
    }
    public static int s(int[] arr,int i,int j)
    {
        if(i==j)
        {
            return 0;
        }
        return Math.min(f(arr,i+1,j),f(arr,i,j-1));
    }

三,动态规划

思路类似于换钱的方法数

public static int win2(int[] arr)
    {
        if(arr==null||arr.length==0)
        {
            return 0;
        }
        int[][] f=new int[arr.length][arr.length];
        int[][] s=new int[arr.length][arr.length];
        for(int j=0;j<arr.length;j++)
        {   //对角线位置 
            f[j][j]=arr[j];
            for(int i=j-1;i>=0;i--)
            {
               f[i][j]=Math.max(arr[i]+s[i+1][j],arr[j]+s[i][j-1]);
               s[i][j]=Math.min(f[i+1][j],f[i][j-1]);
            }
        }
        
        return Math.max(f[0][arr.length-1],s[0][arr.length-1]);
    }