C++ DP solution with explanation


  • 15
    H

    Store the maximum score player1 can get for any sub array [i, j]

    Given an array A[i, j], player 1 can either take the first number A[i] or A[j], after that, it forms a new arrayA[i+1, j] or A[i, j-1] accordingly and it is player2's turn to pick up. The maximum score that player1 can get from the the sub arrays will be the larger one left by player2. So,

    DP formula:
    dp(i, j) = max(sum(i, j-1) - dp(i, j-1) + nums[j], sum(i+1, j) - dp(i+1, j) + nums[i])

    Because sum(i, j-1) + nums[j] = sum(i, j) = nums[i] + sum(i+1, j), the formula can be simplified to
    dp(i, j) = max(sum(i, j) - dp(i, j-1), sum(i, j) - dp(i+1, j))

    More simpler:
    From dp(i, j) = max(sum(i, j) - dp(i, j-1), sum(i, j) - dp(i+1, j)), each dp(i, j) contains sum(i, j), then if we subtract the sum, it should have no impact to final result.

    Thanks to @coder2 point out that the mistake of the dp formula deduction.
    If we do more deduction, we can eliminate the sum(i, j) from the formula:
    Instead of storing the maximum score that player 1 can get in each sub array, we can store the diff between player1 and player 2. For example: if player 1 get A, player 2 get B, we can use dp' to store A-B.

    if A = dp(i, j), then B = sum(i, j) - dp(i, j)

    So dp'(i, j) = dp(i, j) - ( sum(i, j) - dp(i, j) ) = 2*dp(i, j) - sum(i, j), so
    2*dp(i, j) = dp'(i, j) + sum(i, j) (this will be used below)

    dp'(i, j) = dp(i, j) - ( sum(i, j) - dp(i, j) ) = 2dp(i, j) - sum(i, j)
    = 2 * max( sum(i, j) - dp(i, j-1), sum(i, j) - dp(i+1, j) ) - sum(i, j)
    = max(sum(i, j) - 2*dp(i, j-1), sum(i, j) - 2*dp(i+1, j) )
    = max(sum(i, j) - ( dp'(i, j-1) + sum(i, j-1) ), sum(i, j) - ( dp'(i+1, j) + sum(i+1, j)))
    = max(sum(i, j) - sum(i, j-1) - dp'(i, j-1), sum(i, j) - sum(i+1, j) - dp'(i+1, j))
    = max(nums[j] - dp'(i, j-1), nums[i] - dp'(i+1, j))

    Final formula: dp(i, j) = max(nums[j] - dp(i, j-1), nums[i] - dp(i+1, j))

    class Solution {
    public:
        bool PredictTheWinner(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> dp(n, vector<int>(n)); // use to keep the score gap between player1 and player2
            for (int i = 0; i < n; i++) dp[i][i] = nums[i];
            for (int i = 1; i < n; i++) {
                for (int j = 0; j+i < n; j++) {
                    dp[j][j+i] = max(nums[j+i]-dp[j][j+i-1], nums[j]-dp[j+1][j+i]);
                }
            }
            return dp[0][n-1] >= 0; // player1 get more score points than player2
        }
    };
    

  • 0
    C

    Very nice one, brilliant DP formula. I was thinking about similar thing but getting stuck at how to properly compute the maximum that player 1 can obtain in sub-game [i, j].

    I didn't think of sum[i-1][j] - dp[i-1][j] could mean the score player 1 could get after picking the left number and vice versa.

    Nice explanation!!! Thank you!!!


  • 0
    H
    This post is deleted!

  • 0

    what is the meaning of dp'[i][j] after final simplification?


  • 0
    C

    Why return dp[0][n-1] >= 0;?

    If dp is to store the maximum score player1 can get for any sub array [i, j], shouldn't it tell whether this dp[0][n-1]*2 be bigger than sum of all elements? Thanks


  • 0
    H

    @coder2 Thanks for pointing out the mistake. I have updated the explanation with full deduction process


  • 0
    H

    @0x0101 Just updated the comments. dp' is storing the difference value between player1 and player2. Please refer to the new deduction steps above. Sorry for the confusions. Hope that helps.


  • 0
    C

    Why is my solution wrong? Why the order of the two loops would matter ?Thanks

        bool PredictTheWinner(vector<int>& nums) {
    int n = nums.size();
    //difference of player one who first starts minus player two in the range of [i,j]
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int i=0; i<n; i++){
        dp[i][i]=nums[i];
    }
    
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            dp[i][j] = max(nums[j]-dp[i][j-1], nums[i] - dp[i+1][j]);
        }
    }
    
    return dp[0][n-1]>=0;        
    
        }
    }
    
    return dp[0]

  • 0
    H

    @coder2 The essential of DP is to solve smallest problem first and then solve larger ones based on the results of smaller ones. Your code is repeatedly applying dp formula from sub array with 2 elements to n elements.
    Given [1, 2, 3, 4, 5]
    Correct way:
    i=1: [1, 2] -> [2, 3] -> [3, 4] -> [4, 5]
    i=2: [1, 2, 3] -> [2, 3, 4] -> [3, 4, 5]
    i=3: [1, 2, 3, 4] -> [2, 3, 4, 5]
    i=4: [1, 2, 3, 4, 5]

    Your code:
    i=0: [1, 2] -> [1, 2, 3] -> [1, 2, 3, 4] -> [1, 2, 3, 4, 5]
    i=1: [2, 3] -> [2, 3, 4] -> [2, 3, 4, 5]
    ...

    This is obviously wrong.


  • 0
    C

    Thank you very much. I changed the loop and found the following loop is easier for me to understand. It's more like 区间dp, anyone knows English term for this? Thanks

    bool PredictTheWinner(vector<int>& nums) {
    int n = nums.size();
    //difference of player one who first starts minus player two in the range of [i,j]
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int i=0; i<n; i++){
        dp[i][i]=nums[i];
    }
    
    for (int len=1; len<n; len++){
        for (int i=0, j=len; j<n; i++, j++){
            dp[i][j] = max(nums[j]-dp[i][j-1], nums[i] - dp[i+1][j]);
        }
    }
    
    return dp[0][n-1]>=0;        
    }

  • 0
    N

    Thanks we can reach the formula directly by noticing it is a minmax problem.
    Therefore when player 2 gains points player one loses them.

    define:
    dp(i,j) - by how much player one is beating player 2 if he plays an array starting at i and ending with j.

    step:
    dp(i,j) = max( nums[j] //--player 1 takes j--//- dp(i, j- 1) //--player 2 takes the best out of i, j-1/--/,
    nums[i] //--player 1 takes i--// - dp(i+1,j) //--player 2 takes the best out of i+1, j--//)


Log in to reply
 

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