Guest User

iterative

a guest
Feb 11th, 2023
299
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     bool PredictTheWinner(vector<int>& a) {
  4.         const int n = (int)a.size();
  5.         int sm = 0;
  6.         for(int i = 0; i < n; i++) sm += a[i];
  7.        
  8.         int dp[n][n][2];
  9.         for(int j = 0; j < n; j++) {
  10.             for(int i = 0; i + j < n; i++) {
  11.                 for(int t: {0, 1}) {
  12.                     if(t) {
  13.                         dp[i][i + j][t] = min(
  14.                             (i + 1 > i + j? 0: dp[i + 1][i + j][1 - t]),
  15.                             (i > i + j - 1? 0: dp[i][i + j - 1][1 - t])
  16.                         );
  17.                     } else {
  18.                         dp[i][i + j][t] = max(
  19.                             (i + 1 > i + j? 0: dp[i + 1][i + j][1 - t]) + a[i],
  20.                             (i > i + j - 1? 0: dp[i][i + j - 1][1 - t]) + a[i + j]
  21.                         );
  22.                     }
  23.                 }
  24.             }
  25.         }
  26.  
  27.         int res = dp[0][n - 1][0];
  28.         return res >= sm - res;
  29.     }
  30. };
Advertisement
Add Comment
Please, Sign In to add comment