| 73 | |
| 74 | |
| 75 | class Solution: |
| 76 | def PredictTheWinner(self, nums: List[int]) -> bool: |
| 77 | # 2-D array to store |
| 78 | dp = [[0] * len(nums) for _ in range(len(nums))] |
| 79 | |
| 80 | # If there is only 1 value in the array then 1st player takes it has arr[0] and 2nd player has 0 |
| 81 | #so we store (arr[i],0)->(first_player_score,second_player_score) |
| 82 | for q in range(len(nums)): |
| 83 | dp[q][q] = (nums[q], 0) |
| 84 | |
| 85 | # To fill the dp from 0th row and 1st column |
| 86 | for i in range(1, len(nums)): |
| 87 | # As we need to move to column+1 and row+1 we use k for rows so we incerment k+=1 |
| 88 | k = 0 |
| 89 | for j in range(i, len(nums)): |
| 90 | # we check if 1st possible(taking starting element in the array) way gives us higher value if yes we take it |
| 91 | if nums[k] + dp[k + 1][j][1] >= nums[j] + dp[k][j - 1][1]: |
| 92 | dp[k][j] = (nums[k] + dp[k + 1][j][1], dp[k + 1][j][0]) |
| 93 | else: |
| 94 | dp[k][j] = (nums[j] + dp[k][j - 1][1], dp[k][j - 1][0]) |
| 95 | k+=1 |
| 96 | |
| 97 | # we compare scores in the final end if 1st player has >= score of 2nd player we return True else False |
| 98 | if dp[0][len(nums)-1][0]>=dp[0][len(nums)-1][1]: |
| 99 | return True |
| 100 | return False |
nothing calls this directly
no outgoing calls
no test coverage detected