Sponsored
Sponsored
This approach involves using recursion to explore all possible decisions by each player. With each choice, the players reduce the size of the array by selecting an element from either the start or end. Memoization is used to store intermediate results to minimize computational overhead by avoiding repeated calculations.
Time Complexity: O(n²) - Each state (i, j) is computed once.
Space Complexity: O(n²) - Intermediate results are stored in the memoization table.
1def PredictTheWinner(nums):
2
3 def calculate(i, j):
4 if i == j:
5 return nums[i]
6 if memo[i][j] != -1:
7 return memo[i][j]
8 pick_i = nums[i] - calculate(i + 1, j)
9 pick_j = nums[j] - calculate(i, j - 1)
10 memo[i][j] = max(pick_i, pick_j)
11 return memo[i][j]
12
13 length = len(nums)
14 memo = [[-1 for _ in range(length)] for _ in range(length)]
15 return calculate(0, length - 1) >= 0This solution defines a helper function calculate(i, j) which returns the best possible score a player can achieve from the subarray nums[i..j]. The player picks either the start or the end of the subarray. The opponent then plays optimally on the remaining subarray.
The recursive formula is max(nums[i] - calculate(i+1, j), nums[j] - calculate(i, j-1)), where the player's score is reduced by the opponent's optimal score. Memoization stores the results of calculate(i, j) calls to avoid recomputation.
This approach utilizes dynamic programming to solve the problem iteratively. Instead of recursion, it fills up a DP table where each entry represents the best possible score difference a player can achieve for a subarray defined by its boundaries.
Time Complexity: O(n²) - The table is filled once for every distinct range.
Space Complexity: O(n²) - The DP table consumes space proportional to n².
1defThe Python solution involves initializing a 2D array dp where dp[i][j] stores the maximum score difference a player can achieve for nums[i...j]. We fill this table bottom-up, considering all possibilities by iterating over lengths of subarrays and their starting indices.