Optimal Game Strategy (Array Ends)

Approach Tips

**Key Insight:** This is an interval DP problem. The trick is thinking in terms of "score difference" rather than tracking both players separately. **State Definition:** `dp[i][j]` = maximum score difference the **current player** can achieve from subarray `arr[i..j]` **Recurrence:** ``` dp[i][j] = max( arr[i] - dp[i+1][j], // pick left: gain arr[i], opponent gets dp[i+1][j] arr[j] - dp[i][j-1] // pick right: gain arr[j], opponent gets dp[i][j-1] ) ``` The subtraction is the key insight — after you pick, the opponent becomes the "current player" and their best result *subtracts* from yours. **Base case:** `dp[i][i] = arr[i]` (only one element, current player takes it) **Answer:** `dp[0][n-1] >= 0` means Player 1 can win or tie. ```python def optimal_score(arr): n = len(arr) dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = arr[i] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = max( arr[i] - dp[i+1][j], arr[j] - dp[i][j-1] ) return dp[0][n-1] # positive = P1 wins ``` **Complexity:** O(n²) time, O(n²) space. Can be optimized to O(n) space since we only need the previous diagonal. **What interviewers look for:** - Can you identify this as interval DP? (Many try greedy first — greedy fails) - The "score difference" formulation (much cleaner than tracking both players) - Filling the DP table diagonally (by subarray length) - Can you explain *why* greedy fails? (Always picking the larger end doesn't account for what it opens up for the opponent) **Follow-up questions:** - What if there are 3+ players? - What if you can pick from both ends (take up to K from either side)? - Can you reconstruct the actual moves, not just the score?