LeetCode 1563: Stone Game V
Problem Description
Explanation:
To solve this problem, we can use dynamic programming with memoization. We can define a recursive function that simulates the game for each possible split of stones. At each step, we calculate the score that Alice can obtain and store it in a memoization table to avoid redundant calculations. We need to consider all possible splits of stones to maximize Alice's score.
- Create a memoization table to store the maximum score Alice can obtain for a given range of stones.
- Define a recursive function that takes the range of stones as input and calculates the maximum score Alice can obtain.
- At each step, consider all possible splits of the range of stones, calculate the score for Alice, and store the maximum score in the memoization table.
- Return the maximum score that Alice can obtain starting from the entire range of stones.
Time Complexity: O(n^3) where n is the number of stones in the input array.
Space Complexity: O(n^2) for the memoization table.
:
Solutions
class Solution {
public int stoneGameV(int[] stoneValue) {
int n = stoneValue.length;
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + stoneValue[i];
}
int[][] memo = new int[n][n];
return dfs(0, n - 1, prefixSum, memo);
}
private int dfs(int left, int right, int[] prefixSum, int[][] memo) {
if (left == right) return 0;
if (memo[left][right] > 0) return memo[left][right];
int result = 0;
for (int mid = left; mid < right; mid++) {
int leftSum = prefixSum[mid + 1] - prefixSum[left];
int rightSum = prefixSum[right + 1] - prefixSum[mid + 1];
if (leftSum <= rightSum) {
result = Math.max(result, leftSum + dfs(left, mid, prefixSum, memo));
}
if (leftSum >= rightSum) {
result = Math.max(result, rightSum + dfs(mid + 1, right, prefixSum, memo));
}
}
memo[left][right] = result;
return result;
}
}Loading editor...