486. Predict the Winner

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

解题思路：

1. dp[j] 代表数组从index of 0 到 index of j plaryer1 比player2大多少，然后就能通过
   dp【j】是否>0 判断plaryer1大多少
2. 核心是dp[j] = Math.max(nums[i] - dp[j], num[j] - dp[j - 1]); nums[i] 代表数组value at index of 0, nums[j] represents the arrray's value at index of j. dp[j] represents the winner value (player1 - player2) from index of i +1 to j; dp[j - 1] represents the winner value (player1 - player2) from index of i to j - 1.

class Solution {
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]);
        }
    }
    return dp[len - 1] >= 0;
}

}