#877-石子游戏

'''
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 
这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
'''

#解法一
'''
1.由于是偶数堆，那么最左边就是奇数位置，最后一位就是偶数位置。
2.那么不管先手取最左边还是最右边，先手的人总可以一直选择奇数位置或者偶数位置的石堆，比如说，先选择了
	最左边的，那么后者就只能选择偶数位置的。
3.这样先手者就可以决定，选择偶数位置的石堆，或者奇数位置的石堆，又由于石头总数是奇数，那么一定有一个选择
	是更多的，先手者就一定能赢。
return True
'''

#解法二: 动态规划
'''
原问题可以拆分成子问题。
令dp[i][j]表示从第i位到第j位，先选择的人最多能比后面选择的人多多少个石头，那么就有递归式：
	dp[i][j] = max(A[i]-dp[i+1][j], A[j]-dp[i][j-1])
上面这个式子表示，可以先选第i个石堆，那么后者一定在第i+1个位置到第j个位置中执行最优的选择，也就是dp[i+1][j]，
总之上面递归式一定成立。这样先手选第i个石堆，最后得到的石头比对方多A[i]-dp[i+1][j]。从两个选择中选择更优的一种。

通过动态规划求解这个问题，显然要采用一个二维数组（注意i<j，所以实际上是一个上角阵）来记录每
一个dp[i][j]的值：
	1.建立一个n*n的二维数组，对角线上依次赋值输入的各个石堆的数目。
	2.由递推式我们知道，每个dp[i][j]，要么和他左边的值dp[i][j-1]有关，要么和他下边的值dp[i+1][j]有关，
		因此我们每次从第一列开始遍历列，对于每一列又从下向上开始遍历行，更新dp[i][j]的值。
	3.最终dp[0][n-1]就是题目要求的答案
'''
class Solution(object):
    def stoneGame(self, piles):
        """
        :type piles: List[int]
        :rtype: bool
        """
        #return True
        if not piles:
        	return False
        n = len(piles)
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
        	dp[i][i]=piles[i]
        for j in range(1,n):
        	for i in range(j-1,-1,-1):
        		dp[i][j] = max(dp[i][i]-dp[i+1][j],dp[j][j]-dp[i][j-1])
        return dp[0][n-1]>0
