# Java DP O(N) Space with explanation

• ``````    public boolean PredictTheWinner(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
for(int i = len-1; i >= 0; i--) {
for(int j = i; j < len; j++) {
if(i == j) dp[j] = nums[i];
else dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j-1]);
}
}
if(dp[len-1] >= 0) return true;
else return false;
}
``````

Given array [2,3,256,255,2]
If player 1 can get more scores, he will win. That is if score_player_1 - score_player_2 >= 0. Player 1 will win.
And the player 1 picks numbers first.
So we refine the question: how many scores player 1 can win with the given array? Assume each player plays to maximize his score.
If the number is non-negative, player 1 will win.
With this example we can have: array[0,4] = max(nums[0] - array[1,4], nums[4] - array[1,3]), where dp[0,4] means the max scores player 1 can win.
So we can solve this problem with dynamic programming.
O(N*N) Space solution is as follows:

``````        int len = nums.length;
int[][] dp = new int[len][len];
for(int i = len-1; i >= 0; i--) {
for(int j = i; j < len; j++) {
if(i == j) dp[i][j] = nums[i];
else dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
}
}
if(dp[0][len-1] >= 0) return true;
else return false;
``````

Any question is welcome, I will try my best to explain.

• @yli0-umass-edu how can you construct the double for loop, as I get stuck on how to write the for loop.

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