Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

486. Predict the Winner

Time: $O(n^2)$

Space: $O(n^2)$

			


class Solution {
 public:
  bool PredictTheWinner(vector<int>& nums) {
    const int n = nums.size();
    // dp[i][j] := max number you can get more than your opponent in nums[i..j]
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; ++i)
      dp[i][i] = nums[i];

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
      }

    return dp[0][n - 1] >= 0;
  }
};




			


class Solution {
  public boolean PredictTheWinner(int[] nums) {
    final int n = nums.length;
    // dp[i][j] := max number you can get more than your opponent in nums[i..j]
    int[][] dp = new int[n][n];

    for (int i = 0; i < n; ++i)
      dp[i][i] = nums[i];

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
      }

    return dp[0][n - 1] >= 0;
  }
}




			


class Solution {
 public:
  bool PredictTheWinner(vector<int>& nums) {
    const int n = nums.size();
    vector<int> dp = nums;

    for (int d = 1; d < n; ++d)
      for (int j = n - 1; j - d >= 0; --j) {
        const int i = j - d;
        dp[j] = max(nums[i] - dp[j],       // Pick left num
                    nums[j] - dp[j - 1]);  // Pick right num
      }

    return dp[n - 1] >= 0;
  }
};