排成一条线的硬币博弈问题

public int getWinValue(int[] arr) {
        int n = arr.length;
        int low = 0;
        int high = n - 1;
        int turn = 0;
        int max = 0;
        int sum = 0;
        
        for(int i = 0; i < n; i ++){
            sum += arr[i];
        }
        
        while(low <= high){
            if(turn++ % 2 == 0){
                max += Math.max(arr[low], arr[high]);
            }
            
            if(arr[low] > arr[high]){
                low ++;
            }else{
                high --;
            }
        }
        
        return Math.max(max, sum-max);
    }

class Solution {
private:
    int memorized_dfs(int i, int j, vector<vector<int> > &dp, vector<int> &A) {
        if (i == j)
            return dp[i][j] = A[i];
        else if (i > j)
            return 0;
        
        int v = max(min(A[i] + memorized_dfs(i + 2, j, dp, A),			/* 先手拿左边, 后手拿剩下的左边 */
                        A[i] + memorized_dfs(i + 1, j - 1, dp, A)),		/* 先手拿左边, 后手拿剩下的右边 */
                    min(A[j] + memorized_dfs(i + 1, j - 1, dp, A),		/* 先手拿右边, 后手拿剩下的左边 */
                        A[j] + memorized_dfs(i, j - 2, dp, A)));		/* 先手拿右边, 后手拿剩下的右边 */
        
        return dp[i][j] = v;
    }
public:
 /**
 *	得到硬币博弈问题的获胜分值
 *	输入：代表硬币排列情况的数组arr
 *	返回：硬币博弈问题的获胜分值
 */
 int getWinValue(vector<int> arr, int len) {
 vector<vector<int> > dp(len, vector<int>(len, -1));
        int sum = 0;
        for (int i = 0; i < arr.size(); ++i)
            sum += arr[i];
        
        int first = memorized_dfs(0, len - 1, dp, arr);
        int second = sum - first;
        
        return max(first, second);
    }
};

class Solution {
public:
	/**
	 *	得到硬币博弈问题的获胜分值
	 *	输入：代表硬币排列情况的数组arr
	 *	返回：硬币博弈问题的获胜分值
	 */
	int getWinValue(vector<int> arr, int len) {
        vector<vector<int>> dp(len,vector<int>(len,0));
        vector<int> sum(len,0);
        sum[0] = arr[0];
        for(int i=0;i<len;i++){
            dp[i][i] = arr[i];
            if(i>0)
                sum[i] = arr[i]+sum[i-1];
        }
        int j;
        for(int l=1;l<len;l++)
            for(int i=0;i+l<len;i++){
                j = i+l;
                dp[i][j]=sum[j]-sum[i-1]-min(dp[i+1][j],dp[i][j-1]);
            }
        return dp[0][len-1]>sum[len-1]-dp[0][len-1]?dp[0][len-1]:sum[len-1]-dp[0][len-1];
    }
    int min(int a,int b){
        if(a>b)
            return b;
        else
            return a;
    }
};

public static int getWinValue(int[] arr){
		int low = 0;
		int higth = arr.length-1;
		int turn=0,sum = 0,max=0;
		
		//计算总面额
		for(int i=0; i<arr.length; i++){
			sum += arr[i];
		}
		
		while(low <= higth){
			//玩家1取数
			if(turn++ %2 == 0){//玩家1取的顺序是第0,2,4,6...次
				max += Math.max(arr[low], arr[higth]);
			}
			
			//移动数组指针
			if(arr[low] > arr[higth]){//说明上一步取的是arr[low]
				low++;
			}
			else if(arr[low] < arr[higth]){//说明上一步取的是arr[higth]
				higth--;
			}
			else if(arr[low] == arr[higth]){//比如arr[8,10,3,2,6,3],玩家1更乐意取左边的3而不是右边的,这样保证下下一步玩家1可取到6
				if(arr[low+1] >= arr[higth-1]){
					higth--;
				}else{
					low++;
				}
			}
			
		}
		
		
		return Math.max(max, sum-max);
	}
	

public class Solution {
	public int getWinValue(int[] arr) {
		int fh=0, sh=0,sum=0;
		for(int i=0;i<arr.length;i++){
			sum+=arr[i];
		}
		fh=getFirstHandMaxValue(arr);
		sh=sum-fh;
		
        
        if(fh>=sh)
            return fh;
        else
            return sh;

	}
	
	private int getFirstHandMaxValue(int[] arr){
		int fh=0;
	
        int length = arr.length;       
        if(length==1){
        	fh=arr[0];
        }else{        
        	int sum1=0;
        	int sum2=0;
        	int[] subarr1=new int[length-1];
        	int[] subarr2=new int[length-1];
        	for(int i=0;i<length-1;i++){
        		subarr1[i]=arr[i+1];
        		subarr2[i]=arr[i];
        		sum2+=arr[i];
        		sum1+=arr[i+1];
        	}
        	
        	fh=Math.max(arr[0]+sum1-getFirstHandMaxValue(subarr1), arr[length-1]+sum2-getFirstHandMaxValue(subarr2));
        	
        }
		return fh;
        }
	
	public static void main(String[] args){
		Solution s = new Solution();
		int[] arr = {1,9,1,9,1};
		System.out.print(s.getWinValue(arr));
	}
}

自己写的可是系统检测和别人的相似了

class Solution {
public:
    /**
     *  得到硬币博弈问题的获胜分值
     *  输入：代表硬币排列情况的数组arr
     *  返回：硬币博弈问题的获胜分值
     */
    int getWinValue(vector<int> arr, int len) {
         
        int a[len][len],  //a的最高得分
            b[len][len];  //b的最高得分
         
        for(int j=0;j<len;j++){
            for(int i=j;i>=0;i--){
                if(i==j){
                    a[i][j]= arr[i];
                    b[i][j]=0;
                }
                else{
                    a[i][j]= max(arr[i]+b[i+1][j],arr[j]+b[i][j-1]);
                    b[i][j]= arr[i]+a[i+1][j]+b[i+1][j]-a[i][j];
                     
                }
                 
            }
        }
         
        return max(a[0][len-1], b[0][len-1]);
 
    }
     
     
    int max(int a, int b){
        return a>b? a:b;
    }
};

int WonerPerson(int arr[],int n)//比较函数，返回胜者的分数
{
    int i=0,j=n-1;
    int sum1=0,sum2=0;//定义甲（sum1）,乙（sum2）的计数器
    while(i<=j){
        if(arr[i]>=arr[j]) {sum1+=arr[i];i++;}
        else {sum1+=arr[j];j--;}

        if(arr[i]>=arr[j]) {sum2+=arr[i];i++;}
        else {sum2+=arr[j];j--;}
    }
    return sum1>sum2?sum1:sum2;
}
int main (void)
{
    int n=4;
    int arr[]={7,6,5,9};
    int king=WonerPerson(arr,n);
    printf("%5d",king);
    system("pause");
    return 0;
}