# Java DP solution with two matrices, welcome for optimization

• The basic idea is to build up two 2D array for caching, the index of row indicate start point and the index of column indicate end point.

``````public class Solution {
public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
if (n == 1) return  true;

int[][] myTurn = new int[n][n];
int[][] notMyTurn = new int[n][n];

//use a sum array to easier calculate the value in notMyTurn after myTurn is calculated
int[] sums = new int[n];
sums[0] = nums[0];
for (int i = 1; i < n; i++) {
sums[i] = sums[i - 1] + nums[i];
}

//On the diagonal, like (5, 5) which start and end at the same point, so if it's my turn
// I can always take the value and leave 0 to the other.
for (int i = 0; i < n; i++) {
myTurn[i][i] = nums[i];
notMyTurn[i][i] = 0;
}

// We go through then length of the array
for (int j = 1; j < n; j++) {
//we start from point on the diagonal and go up
for (int i = j - 1; i >= 0; i--) {
myTurn[i][j] = Math.max(nums[i] + notMyTurn[i + 1][j], nums[j] + notMyTurn[i][j - 1]);
int sum = sums[j] - (i > 0? sums[i - 1] : 0);
notMyTurn[i][j] = sum - myTurn[i][j];
}
}

return myTurn[0][n - 1] >= notMyTurn[0][n - 1];
}
}
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.