Leetcode Problem 1406. Stone Game III

1406. Stone Game III

Leetcode Solutions

Approach: Bottom-Up Dynamic Programming

  1. Let n be the number of stones.
  2. Declare the array dp of size n + 1.
  3. Set dp[n] = 0 (the base case of the DP).
  4. Iterate i from n - 1 to 0:
    • Set dp[i] = stoneValue[i] - dp[i + 1] (take one stone).
    • If i + 2 <= n, update dp[i] with stoneValue[i] + stoneValue[i + 1] - dp[i + 2] (take two stones) if it's larger.
    • If i + 3 <= n, update dp[i] with stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3] (take three stones) if it's larger.
  5. If dp[0] > 0, Alice wins.
  6. If dp[0] < 0, Bob wins.
  7. If dp[0] = 0, it is a tie.
UML Thumbnail

Approach: Top-Down Dynamic Programming (Memoization)

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...