# Clean 3ms C++ DP solution with detailed explanation

• This problem can be solved in DP.

Let first outline the DP state:

dp[i][j] means that for a sub-game in between [i, j] inclusive, the maximum score that Player 1 could get.

Our final goal is to find out whether Player 1 could score more than half of the total score in the game between [0, n-1], or in other words the dp[0][n-1]. Another thing to notice is that, because Player 1 and Player 2 pick numbers one after each other, this means:

If dp[i][j] means maximum score Player 1 could get between [i, j] then dp[i-1][j] could mean the maximum score Player 2 could get between [i-1, j], and same thing for dp[i][j-1].

Another more important thing based on the above statement is that:

The sum[i-1][j] - dp[i-1][j] means the maximum score Player 1 can get between [i-1, j] after he picks nums[i] in between [i, j]. Also the same rule applies to dp[i][j-1].

Thus we have the following induction rule for this DP solution:

pickLeft = nums[i] + sum[i-1][j] - dp[i-1][j] //if left number is picked
pickRight = nums[j] + sum[i][j-1] - dp[i][j-1] //if right number is picked
dp[i][j] = max(pickLeft, pickRight)

Of course we can treat i == j and i == j-1 as special cases:
dp[i][j] = nums[i] // if i == j
dp[i][j] = max(nums[i], nums[j) // if i == j-1

For space complexity reason the sum[i][j] can be replaced with prefixSum.
sum[i][j] = prefixSum[j] - prefixSum[i-1]

``````    bool PredictTheWinner(vector<int>& nums) {
vector<vector<int>> score(nums.size(), vector<int>(nums.size()));
vector<int> prefixSum(nums.size()+1);
prefixSum[0] = 0;
for (int i=0; i<nums.size(); i++) {
prefixSum[i+1] = prefixSum[i] + nums[i];
}

for (int len=1; len<=nums.size(); len++) {
for (int lhs=0; lhs+len-1<nums.size(); lhs++) {
int rhs = lhs + len - 1;
if (lhs == rhs) {
score[lhs][rhs] = nums[lhs];
} else if (lhs == rhs-1) {
score[lhs][rhs] = max(nums[lhs], nums[rhs]);
} else {
int pickLeft = nums[lhs] + prefixSum[rhs+1] - prefixSum[lhs+1] - score[lhs+1][rhs];
int pickRight = nums[rhs] + prefixSum[rhs] - prefixSum[lhs] - score[lhs][rhs-1];
score[lhs][rhs] = max(pickLeft, pickRight);
}
}
}

return score[0][nums.size()-1] >= prefixSum.back()/2 + prefixSum.back()%2;
}
``````

• Hi @code9yitati , thank you for your nice explanation.

I wrote a Java solution which is pretty similar to yours. The only difference is that when performing the loop, my `i` begins with its max value, while your `lhs` begins with its min value.

``````    public boolean PredictTheWinner(int[] nums) {

int n = nums.length;
// dp[i][j] is the max value a player can get between [i, j]
int[][] dp = new int[n][n];

int[] prefixSum = new int[n + 1];
for (int i=1; i<n+1; ++i) {
prefixSum[i] = prefixSum[i-1] + nums[i-1];
}

// i begins with the max value
for (int i=n-1; i>=0; --i) {
for (int j=i; j<n; ++j) {
if (i == j) {
dp[i][j] = nums[i];
} else if (i + 1 == j) {
dp[i][j] = Math.max(nums[i], nums[j]);
} else {
int maxSumL = prefixSum[j+1] - prefixSum[i+1];
int lhs = nums[i] + maxSumL - dp[i + 1][j];

int maxSumR = prefixSum[j] - prefixSum[i];
int rhs = nums[j] + maxSumR - dp[i][j - 1];

dp[i][j] = Math.max(lhs, rhs);
}
}
}

return dp[0][n-1] >= (prefixSum[n] - dp[0][n-1]);
}
``````

Even though the results come out to be the same, I'm confused why you let `lhs` be ascending in the loop. Here is my arguments:

Given that the following induction rules require the value of `dp[i+1][j]` to calculate `dp[i][j]`, it's natural to loop a descending `i` , while it is unintuitive (very tricky + hard to verify) to pick up the opposite direction (though it happens to work here).

``````// You put dp[i-1][j] in the first induction rule, but based on your code, I believe it's a typo.
pickLeft = nums[i] + sum[i-1][j] - dp[i+1][j] //if left number is picked
pickRight = nums[j] + sum[i][j-1] - dp[i][j-1] //if right number is picked
dp[i][j] = max(pickLeft, pickRight)
``````

I'm just curious, how did you come with the decision to loop `lhs` ascendingly? I notice other posts go the same way but without further explanation.

Thanks:)

• A clear explanation and easy to understand!
But your space complexity could be reduced again: your dp[i][j] can be simplified.I did some change upon your code:
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
vector<int> ret(nums);
vector<int> sum={0};
for(auto num:nums){
sum.push_back(sum.back()+num);
}
for(int len=2;len<=nums.size();++len){
for(int left=0;left+len-1<nums.size();++left){
int right=left+len-1;
if(left==right-1){
ret[left]=max(ret[left],ret[right]);
}else{
int pickleft=nums[left]+sum[right+1]-sum[left+1]-ret[left+1];
int pickright=nums[right]+sum[right]-sum[left]-ret[left];
ret[left]=max(pickleft,pickright);
}
}
}
return ret[0]>=sum.back()/2+sum.back()%2;
}
};
As you can see,dp[i][j] is produced by dp[i+1][j] and dp[i][j-1].I'm not good in english,here's an example:
dp[0]2:dp[1][2](old ret[1]),dp[0][1](old ret[0]).
dp[i]j:dp[i+1][j](old ret[i+1]),dp[i][j-1](old ret[i]).
and finally,the dp[0][nums.size()-1]becomes ret[0].

• can anybody explain why pickleft and pickright have different formulas in explanation compared to the code ?

• @RunRunCode this is because there is an ascending loop for len. dp[i][j] with a smaller len has already been computed. Therefore, lhs ascending is not a problem here.

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