486. Predict the Winner

 一刷 07/2022

Version #1 DP game theory

Time O(N^2)

Space O(N^2) - space can be optimized to O(N)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Predict the Winner.

Memory Usage: 39.9 MB, less than 87.08% of Java online submissions for Predict the Winner.

class Solution {

    public boolean PredictTheWinner(int[] nums) {

        int len = nums.length;

        int[][] dp = new int[len][len];

        // dp[i][j] - max score diff that we can get between nums [j, i]

        for (int i = 0; i < nums.length; i++) {

            for (int j = i; j >= 0; j--) {

                if (i == j) {

                    dp[i][j] = nums[i];

                } else {

                    // [j, i]

                    dp[i][j] = Math.max(nums[i] - dp[i - 1][j], nums[j] - dp[i][j + 1]);

                }

            }

        }

        return dp[len - 1][0] >= 0;

    }

}