I won't say much about the importance of algorithms. If you want to go to a large factory, you must go through the interview of basic knowledge and business logic + algorithm. So, in order to improve the algorithm ability, this official account will be followed up every day to do an algorithm question, and the topic will be selected from LeetCode.

The question we are talking about today is called predicting winners. Let's look at the question first:

https://leetcode-cn.com/problems/predict-the-winner/

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

Give you an integer array nums. Player 1 and player 2 designed a game based on this array.

Player 1 and player 2 take turns in their own rounds, and player 1 takes the lead. At the beginning, the initial score of both players is 0. Each round, players take a number from either end of the array (i.e., Num [0] or num [num.length - 1]), and the number will be removed from the array (array length minus 1). The number selected by the player will be added to his score. When there are no numbers left in the array, the game ends.

If player 1 can be the winner, return true. If two players have equal scores, player 1 is also considered as the winner of the game and returns true. You can assume that each player's play will maximize his score.

Example

Example 1:
Input: nums = [1,5,2]
Output: false
 Explanation: at the beginning, player 1 can choose from 1 and 2.
If he chooses 2 (or 1), player 2 can choose from 1 (or 2) and 5. If player 2 selects 5, player 1 has only 1 (or 2) left.
Therefore, the final score of player 1 is 1 + 2 = 3，Player 2 is 5.
Therefore, player 1 will never be a winner and return false . 

Example 2:
Input: nums = [1,5,233,7]
Output: true
 Explanation: Player 1 chooses 1 at the beginning. Player 2 must then choose between 5 and 7. No matter which player 2 chooses, player 1 can choose 233.
Finally, player 1 (234 points) gets more points than player 2 (12 points), so return true，Indicates that player 1 can be a winner.

Problem solving

Represented by DP[I][J], as the forehand, the start and end coordinates of the array are I and j, and the maximum value of the difference between the integral obtained by yourself and that obtained by the opponent.

There is a state transition equation: DP[I][J] = MAX{NUMS[I]-DP[I+1][J], NUMS[J]-DP[I][J-1]}, which is solved by dynamic programming.

/**
 * @Date: 2022/01/01/8:15
 * @Description:
 */
// [1,5233,7] it's not just the biggest. For example, if I take 1 first, no matter which one you take, I will get 233, otherwise if I get 7, you will get 233
// Predict whether player 1 can win.
// Each time they take a number from one end.
// You can assume that each player's play will maximize his score.

class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.PredictTheWinner(new int[]{1, 5, 2}));
    }


    public boolean PredictTheWinner(int[] nums) {
        if (nums == null || nums.length == 0) return true;
        // There is at least one element. Using dynamic programming method.
        // dp[i][j] = max{nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]}
        int[] arr = new int[nums.length];

        for (int i = 1; i <= nums.length; i++) {
            arr[arr.length-i] = nums[nums.length-i]; // Assignment, diagonal.
            for (int j = arr.length-i+1; j < nums.length ; j++) {
                arr[j] = Math.max(nums[nums.length-i]-arr[j],nums[j]-arr[j-1]);
            }
        }
        return arr[nums.length-1]>=0;
    }
}

Well, that's all for today's article. If you feel you have something to gain, please click to read or forward it. Your support is my greatest motivation.

Last tweet:

Leetcode 1-480 question summary, I hope it will be helpful to you!

LeetCode practice 481: Magic string

LeetCode practice 482: key formatting

LeetCode practice 483: minimum good base

LeetCode practice 484: finding permutations

LeetCode problem brushing practice 485: the maximum number of consecutive 1