advance DP

predict_winner.py

class Solution:
    def PredictTheWinner(self, c):
        """
        :type nums: List[int]
        :rtype: bool
        """
        r = len(c)
        t = sum(c)
        s = [[0 for i in range(r)] for j in range(r)]
        for l in range(r): # l is for the length - 1
            for i in range(r-l): # i is the starting index, 
                if l == 0:
                    s[i][l] = c[i]
                elif l == 1:
                    s[i][l] = max(c[i], c[i+l])
                elif l == 2:
                    s[i][l] = max(c[i] + min(c[i+1], c[i+2]), 
                                  c[i+2] + min(c[i+1], c[i]))
                else:
                    s[i][l] = max(c[i] + min(s[i+2][l-2], s[i+1][l-2]), 
                                  c[i+l] + min(s[i][l-2], s[i+1][l-2]))
        return (s[0][r-1] >= (t - s[0][r-1]))