纸牌博弈

# -*- coding:utf-8 -*-
#用first[j][i]表示先选的人能拿到的最高分,second[j][i]来表示后选的人能拿到的最高分
#对于先选者，他有两种选法
#1.若先选者选A[0],则对于后面的1，...,n-1数组，他就变成了后选者，此时能拿到的分为A[0]+S[1][n-1]
#2.若先选者选A[n-1],则对于前面的数组0，...，n-2,同样变为后选者，此时能拿到得分为A[n-1]+S[0][n-2];
#所以 F[0][n-1]=max(A[0]+S[1][n-1],A[n-1]+S[0][n-2])
#对于后选者，他能能到的最高分是受先选者控制的，即他只能选到先选者留给他的最小值，将其转化为数学形式就是
#S[l][r]=min(F[l+1][r],F[l][r-1])
#这里的最小值是先选者留给他的，他只能拿到最小值
class Cards:
    def cardGame(self, A, n):
        first=[[0 for i in range(n)] for i in range(n)]
        second=[[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            first[i][i]=A[i]
            second[i][i]=0
            j=i-1
            while j>=0:
                first[j][i]=max(second[j+1][i]+A[j],second[j][i-1]+A[i])
                second[j][i]=min(first[j+1][i],first[j][i-1])
                j-=1
        return max(first[0][n-1],second[0][n-1])

        return int(max(first[0][n-1],second[0][n-1]))