동적 기획: 게임 승자(一)

비음수조를 정하고 A, B 두 사람이 게임을 하며 수조의 머리나 꼬리에서 원소를 번갈아 꺼내 각자의 화합에 넣고 수조 원소를 다 찾으면 얻은 원소와 가장 큰 유저가 이긴다.주어진 수조에 대해 먼저 시작한 유저가 게임을 이길 수 있느냐고 묻는다(만약 같다면 선수의 유저가 이길 수 있다).
예를 들어 주어진 수조는 [1, 5, 233, 7]이고 A는 첫 번째 단계를 시작하는 유저이다.A는 1 또는 7을 얻을 수 있는데 만약에 A가 먼저 1을 얻으면 [5, 233, 7]가 남는다.B는 5나 7을 얻을 수 있지만 B가 어떤 요소를 취하든지 A는 233을 얻을 수 있기 때문에 A는 게임을 이길 수 있다.
분석: 먼저 가는 유저가 게임을 이기는 것은 먼저 가는 유저의 요소와 수조와 같은 절반보다 큰 것을 요구하는 것이다.
만약에 게임의 절차에 따라 수조를 긴 방향에서 짧은 방향으로 진행하면 한 걸음 한 걸음 다른 선택이 생길 것이다. 가능한 모든 상황을 기록하려면 시간 복잡도와 공간 복잡도가 비교적 높다.
방법1: 이 과정을 거꾸로 하여 주어진 수조에 대해 반대로 짧은 방향에서 긴 방향으로 계산할 수 있다.
dp[i][j][j]로 선수 유저가 획득한 원소를 기록하면 d[i][j] [j] = max(d[i+1] [j] + nums[i], d[j-1] + nums[j]), 그 중에서 d[i+1] [j]는 상대방이 원소를 선택한 결과로 상대방이 확정한 것으로 다음과 같은 두 가지 상황 중 하나일 가능성이 있다. d[i+1] [j] [j] = d[j] [j] [j] 또는 d[i+1] [j] [j] [j] [j] [[j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j또는 d[i][j-1]=d[i][j-2].상대방의 목적은 선수 유저를 최소화하는 것이기 때문에 d[i+1][j]=min(dp[i+2][j], dp[i+1][j-1]), d[i][j-1]=min(dp[i+1][j-1], dp[i][j-2])이다.따라서 dp[i][j]=max(min(dp[i+1][j-1], dp[i+2]]+nums[i],min(dp[i][j-2], dp[i+1][j-1])+nums[j]})
(원소를 선택하는 과정을 역순으로 진행한 것과 같다. 만약에 정서대로라면 마지막과 최대를 위해 한 걸음 한 걸음 선택한 것이 반드시 현재와 가장 큰 원소는 아니다. 그러나 역순으로 하는 과정은 마지막 단계부터 선택하고 한 걸음 한 걸음 현재와 가장 큰 원소를 선택하며 마지막 단계까지 얻은 것이 가장 큰 합이다.
이 과정은 실제적으로minmax 알고리즘의 실현을 위해 나무의 잎사귀를 검색하는 상황부터 (모든 가능한 검색 경로의 종점에서부터) 한 걸음 한 걸음 선수의 주동권을 취하고 최대치를 취하며 상대방의 주동권이라면 최소치를 취한다.뿌리 노드까지 유추하다.
4

   public boolean PredictTheWinner(int[] nums) {
        int n = nums.length, sum = 0;
	if(n % 2 == 0) return true; //           ，                       ，                      
        int[][] dp = new int[n][n];
        for(int i=0; i < n; i++) {
            dp[i][i] = nums[i]; //     ，              
            sum += nums[i];
        }

        for(int j = 0; j < n; j++){
            for(int i = j - 1; i >= 0; i--){
            	int a = (i + 1 < n && j - 1 >= 0) ? dp[i + 1][j - 1] : 0;
		int b = (i + 2 < n) ? dp[i + 2][ j] : 0;
		int c = (j - 2 >= 0) ? dp[i][j - 2] : 0;
                dp[i][j] = Math.max(Math.min(a, b) + nums[i], Math.min(a, c) + nums[j]);
            }
        }

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

방법2: 귀속방법 사용

    public boolean PredictTheWinner(int[] nums) {
        return helper(nums, 0, nums.length-1)>=0;
    }
    private int helper(int[] nums, int s, int e){        
        return s==e ? nums[e] : Math.max(nums[e] - helper(nums, s, e-1), nums[s] - helper(nums, s+1, e)); //            ，      ，     A ，      helper    B-A，         A   ，     num-helper。
    }