Java, using DP


  • 0
    P
    public boolean PredictTheWinner(int[] nums) {
    	int len = nums.length;
    	int[][] dp = new int[len][len];
    	for (int i = 0; i < len; i++) {
    		dp[i][i] = len % 2 == 0 ? -nums[i] : nums[i];
    	}
    	for (int sublen = 2; sublen <= len; sublen++) {
    		for (int i = 0; i + sublen - 1 < len; i++) {
    			if ((len % 2 == 0 && sublen % 2 == 0) || (len % 2 == 1 && sublen % 2 == 1)) {
    				// p1 turn
    				dp[i][i + sublen - 1] = Math.max(nums[i] + dp[i + 1][i + sublen - 1],
    						nums[i + sublen - 1] + dp[i][i + sublen - 2]);
    			} else {
    				// p2 turn
    				dp[i][i + sublen - 1] = Math.min(-nums[i] + dp[i + 1][i + sublen - 1],
    						-nums[i + sublen - 1] + dp[i][i + sublen - 2]);
    			}
    		}
    	}
    //		for (int i = 0; i < len; i++) {
    //			System.out.println(Arrays.toString(dp[i]));
    //		}
    	return dp[0][len - 1] >= 0;
    }
    

Log in to reply
 

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