Leetcode Problem 1690. Stone Game VII

1690. Stone Game VII

Leetcode Solutions

Dynamic Programming - Memoization

  1. Initialize a 2D memoization array dp with dimensions n x n filled with None, where n is the length of the stones array.
  2. Define a recursive function findDifference(start, end) that returns the maximum score difference the current player can achieve from the subarray stones[start:end+1].
  3. If dp[start][end] is not None, return the stored value as the result for the current subproblem.
  4. If start == end, return 0 since there is only one stone left.
  5. Calculate the score difference if the current player removes the leftmost stone and if they remove the rightmost stone, taking into account the score difference the opponent would achieve.
  6. Store the maximum of these two score differences in dp[start][end].
  7. Return dp[start][end] as the result for the current subproblem.
  8. Call findDifference(0, n-1) to get the final result, which is the maximum score difference Alice can achieve.
UML Thumbnail

Greedy Approach (Suboptimal)

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...