Python 61ms DP solution with explanation

  • 0

    The core thought of my solution is as follows:

    1. Assume the array is
      [a1, a2, a3, ..., ak] ----- ①
    2. Player1 picks a1 or ak
    3. Player2 picks from
      [a2, a3, ..., ak] ----- ②
      [a1, a2, ..., ak-1] ----- ③

    So here comes the sub question, assume we have known the player1's best strategy, when he faced array② or array③. It's easy to find player2 will do what player1 did, because player2 want to win the game too, and he can't find a better strategy.

    Now, we can describe the top-down process:

    1. Player1 has two choice:
      s1 = a1 + [player2's strategy when beginning array is ②(because player1's strategy would be use by plalyer2 with beginning array is ①)]
      s2 = ak + [player2's strategy when beginning array is③]
      what he finally choice is:
      s = max(s1, s2)
      because he wants win the game, he need the higher score.
    2. Player2's choice is depend on player1, he has no choice:
      if s1 > s2:
      rs = player1's strategy when beginning array is ②
      rs = player1's strategy when beginning array is ③

    I used a bottom-up method to write the codes, first compute the score when length of numbers is 2, then 3, then 4...

    class Solution:
        def PredictTheWinner(self, nums):
            :type nums: List[int]
            :rtype: bool
            n = len(nums)
            # initialize a n*n*2 matrix, dp[i][k][0] means 
            # for beginning array nums[i:k+1], player1's score, 
            # and dp[i][k][1] means player2's.
            dp = [[[0 for state in range(2)] for i in range(n)] for j in range(n)]
            for i in range(n):
                dp[i][i][0] = nums[i]
            for i in range(1, n):
                #internal from 1 to n-1
                for k in range(n-i):
                    # two strategies of player1
                    p1_1 = nums[k]+dp[k+1][k+i][1]
                    p1_2 = nums[k+i]+dp[k][k+i-1][1]
                    if p1_1 > p1_2:
                        dp[k][k+i][0] = p1_1
                        dp[k][k+i][1] = dp[k+1][k+i][0]
                        dp[k][k+i][0] = p1_2
                        dp[k][k+i][1] = dp[k][k+i-1][0]
            # player1 win the game if the got the same scores.
            return dp[0][n-1][0] >= dp[0][n-1][1]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.