Java DP O(N) Space with explanation


  • 0
    Y
        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.


  • 0
    S

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


Log in to reply
 

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