Most readable C++ Recursion Version, 3ms!


  • 0
    J

    The idea is extremely simple. Player A can either pick front or back to response Player B, i.e. "||". Player B can try both front and back to challenge Player A, i.e. "&&".

    class Solution {
      private:
        enum TURN { A, B };
    
      public:
        bool PredictTheWinner(const vector<int> &nums) {
            if (nums.size() <= 1) {
                return true;
            }
            return dp(nums, 0, nums.size() - 1, 0, 0, A);
        }
    
      private:
        bool dp(const vector<int> &nums, int from, int to_hasEnd, int score_A,
                int score_B, TURN turn) {
            if (from > to_hasEnd) {
                return score_A > score_B;
            }
    
            switch (turn) {
            case A:
                return dp(nums, from + 1, to_hasEnd, score_A + nums[from], score_B,
                          B) ||
                       dp(nums, from, to_hasEnd - 1, score_A + nums[to_hasEnd],
                          score_B, B);
            case B:
                return dp(nums, from + 1, to_hasEnd, score_A, score_B + nums[from],
                          A) &&
                       dp(nums, from, to_hasEnd - 1, score_A,
                          score_B + nums[to_hasEnd], A);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.