100天每日一题（day10）

2020.9.3 晴

不知不觉就9月份了，转眼2020年就只剩下4个月了。。

 

 

题解：感觉又是一道经典的动态规划题。三板斧：

第一板斧：先创建一个二维数组dp[i][j] ，dp[i][j]代表从数组nums[i:j]先手，赢过对方的分数。终止条件：dp[i][j]=nums[i](i=j)，因为只有一个数，先拿就领先这个数的分数

二板斧：状态转移方程：dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])。意思是从右端拿就减去在nums[i+1:j]中后手拿亏的分数，左端同理。

三板斧：判断状态转移方向：从右下角开始，往上一排转移，然后从左往右转移（这里我也不太懂）

class Solution:

    def PredictTheWinner(self, nums: List[int]) -> bool:

            n=len(nums)

            dp=[[0 for i in range(n)]for i in range(n)]

            for i in range(n):

                dp[i][i]=nums[i]

            for i in range(n-2,-1,-1):

                for j in range(i+1,n):

                        print(i,j)

                        geti=nums[i]-dp[i+1][j]

                        getj=nums[j]-dp[i][j-1]

                        dp[i][j]=max(geti,getj)

            if dp[0][n-1]>=0:

                return True

            else:

                return False