Java DP solution with two matrices, welcome for optimization


  • 0
    S

    The basic idea is to build up two 2D array for caching, the index of row indicate start point and the index of column indicate end point.

    public class Solution {
        public boolean PredictTheWinner(int[] nums) {
            int n = nums.length;
            if (n == 1) return  true;
            
            int[][] myTurn = new int[n][n];
            int[][] notMyTurn = new int[n][n];
            
            //use a sum array to easier calculate the value in notMyTurn after myTurn is calculated
            int[] sums = new int[n];
            sums[0] = nums[0];
            for (int i = 1; i < n; i++) {
                sums[i] = sums[i - 1] + nums[i];
            }
            
            //On the diagonal, like (5, 5) which start and end at the same point, so if it's my turn
            // I can always take the value and leave 0 to the other.
            for (int i = 0; i < n; i++) {
                myTurn[i][i] = nums[i];
                notMyTurn[i][i] = 0;
            }
            
            // We go through then length of the array
            for (int j = 1; j < n; j++) {
                //we start from point on the diagonal and go up 
                for (int i = j - 1; i >= 0; i--) {
                    myTurn[i][j] = Math.max(nums[i] + notMyTurn[i + 1][j], nums[j] + notMyTurn[i][j - 1]);
                    int sum = sums[j] - (i > 0? sums[i - 1] : 0);
                    notMyTurn[i][j] = sum - myTurn[i][j];
                }
            }
            
            return myTurn[0][n - 1] >= notMyTurn[0][n - 1];
        }
    }
    

  • 0
    Z
    This post is deleted!

Log in to reply
 

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