486. Predict the Winner

题目链接：

看了discussion里面参考的mit算法视频：

recursion + memo 或者 iteration用dp table

public class Solution {    public boolean PredictTheWinner(int[] nums) {        // // even, always win        // if(nums.length % 2 == 0) return true;                int n = nums.length;        // maximum score play1 can get        int[][] dp = new int[n][n];        int sum = 0;        // base cases        for(int i = 0; i < n; i++) {            dp[i][i] = nums[i];            sum += nums[i];        }        for(int i = 1; i < n; i++) dp[i-1][i] = Math.max(nums[i-1], nums[i]);                // dp recur        for(int i = n - 1; i >= 0; i--) {            for(int j = i + 2; j 
    
     = sum - dp[0][n-1];    }}