Clean 3ms C++ DP solution with detailed explanation


  • 10
    C

    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;
        }
    

  • 1

    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:)


  • 0
    R

    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].


  • 0
    T

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


  • 0
    K

    @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.


Log in to reply
 

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