힘 으로 문 제 를 푸 는 것 - 486. 승 자 를 예측 하 는 것 (분 치 법 사상, 재 귀 하 는 방식 으로 해결 하 는 것)

제목: 486. 승자 예측
점 수 를 나타 내 는 비 마이너스 정수 그룹 을 지정 합 니 다.게이머 1 은 배열 의 임 의 한 끝 에서 점 수 를 얻 은 다음 에 게이머 2 는 남 은 배열 의 임 의 한 끝 에서 점 수 를 얻 은 다음 에 게이머 1 이 점 수 를 얻 습 니 다.매번 한 유 저 는 하나의 점 수 를 얻 을 수 있 고 점 수 를 얻 은 후에 더 이상 얻 을 수 없습니다.남 은 점수 가 없 을 때 까지 게임 이 끝 납 니 다.최종 점수 총계 가 가장 많은 유저 가 이 겼 습 니 다.
점 수 를 나타 내 는 배열 을 지정 하여 게이머 1 이 승자 가 될 지 여 부 를 예측 합 니 다.너 는 모든 게이머 들 의 게임 방법 이 그의 점 수 를 최대 화 할 것 이 라 고 가정 할 수 있다.
예제 1: 입력: [1, 5, 2] 출력: False 설명: 처음에 게이머 1 은 1 과 2 에서 선택 할 수 있 습 니 다.만약 그 가 2 (또는 1) 를 선택한다 면 게이머 2 는 1 (또는 2) 과 5 중에서 선택 할 수 있다.플레이어 2 가 5 를 선택 하면 플레이어 1 은 1 (또는 2) 만 선택 할 수 있 습 니 다.따라서 유저 1 의 최종 점 수 는 1 + 2 = 3 이 고 유저 2 는 5 입 니 다.따라서 유저 1 은 영원히 승자 가 되 지 않 고 False 로 돌아 갑 니 다.
예제 2: 입력: [1, 5, 233, 7] 출력: True 설명: 게이머 1 처음부터 1 을 선택 합 니 다.그리고 플레이어 2 는 5 와 7 중에서 선택해 야 합 니 다.플레이어 2 가 어느 것 을 선택 하 든 플레이어 1 은 233 을 선택 할 수 있 습 니 다.최종 적 으로 플레이어 1 (234 점) 이 플레이어 2 (12 점) 보다 더 많은 점 수 를 얻 었 기 때문에 트 루 로 돌아 가 플레이어 1 이 승자 가 될 수 있 음 을 나타 낸다.
알림:
1 < = 주어진 배열 의 길이 < = 20. 배열 의 모든 점 수 는 마이너스 가 아니 고 10000000 보다 크 지 않 습 니 다.만약 최종 두 유저 의 점수 가 같다 면, 유저 1 은 여전히 승자 이다.
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/predict-the-winner 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
해제
제목 은 최종 점수 총합 을 가장 많이 얻 은 유저 가 승리 하도록 요구한다.
그러면 우 리 는 1 번 게이머 의 점 수 를 2 번 게이머 의 점 수 를 빼 고 최종 총 점 수 를 계산 하여 1 번 게이머 의 승 패 를 나타 낸다.
이 총 득점 이 0 보다 크 면 1 번 유저 가 이기 고 그렇지 않 으 면 1 번 유저 가 진다.
분 치 법 사상 을 이용 하여 문 제 를 분해 한 다음 에 자 문 제 를 재 귀적 으로 해결 하여 최종 적 으로 문제 의 해 를 얻 었 다.Divide and Conquer 사상 및 실제 응용 참조.분해 과정 보기:

Divide 는 점 수 를 선택 할 때마다 수미 두 요소 중 하나 만 선택 할 수 있 기 때문에 원래 의 문 제 를 두 가지 상황 으로 나 눌 수 있다. 첫 번 째 요 소 를 선택 하고 꼬리 요 소 를 선택 하 는 것 이다.첫 번 째 요 소 를 선택 하 든 꼬리 요 소 를 선택 하 든 우 리 는 원 문 제 를 두 개의 키 문제 로 분해 할 수 있다.즉, start, nums [start + 1, end] 또는 end, nums [start, end - 1].

Conquer 는 첫 번 째 요 소 를 선택 했다. 1 번 게이머 의 점 수 는 nums [start] 이 고 2 번 게이머 의 점 수 는 게이머 의 1 점 수 를 구 하 는 서브 문제 nums [start + 1, end] 로 볼 수 있 으 며 재 귀적 으로 해결 할 수 있다.끝 요 소 를 선택 하 십시오: 1 번 유저 의 점 수 는 nums [end] 입 니 다. 2 번 유저 의 점 수 는 유저 의 1 점 수 를 구 하 는 하위 문제 nums [start, end - 1] 로 볼 수 있 습 니 다.이렇게 해서 각각 두 가지 상황 의 1 번 유저 와 2 번 유저 의 점 수 를 구한다.

Combine 의 총 득점 은 1 번 유저 의 득점 에서 2 번 유저 의 득점 을 뺀 것 이다.두 가지 상황 의 총 득점 의 최대 치 는 최종 결과 이다.

코드

class Solution {
public:
    bool PredictTheWinner(vector& nums) {
        int score = accScore(0, nums.size()-1, nums);
        return score >= 0 ? true: false;
    }

    int accScore(int start, int end, vector& nums) {
        if (start == end) {
            return nums[start];
        }
        int preScore = nums[start] - accScore(start+1, end, nums);
        int suffixScore = nums[end] - accScore(start, end-1, nums);

        return max(preScore, suffixScore);
    }
};