leetcode877 Stone Game

사고방식: 욕심 전략이 옳지 않기 때문에 모든 상황을 열거하고 dp를 사용하여 시간의 복잡도를 낮춰야 한다. (이 문제는 수학적 해석이 있어 알렉스가 반드시 이길 수 있음을 증명한다)

alex와lee는 머리와 꼬리가 돌dp로 돌아가며 기록할 때 양쪽을 기록해야 하기 때문에 2차원 그룹 dp[left][right]이다.

[5,3,4,5]를 예로 들면 왼쪽에 [3,4,5], dp[left][right]=piles[left]+dp[left+1][right]?Lee가 가져가야 하기 때문에 이것은 옳지 않다. 나머지 [3,4,5]lee는 머리와 꼬리 중 하나를 가져가야 한다. 실제로alex는 [3,4] 또는 [4,5]에서만 선택할 수 있다. 따라서 dp[left][right]=piles[left]+max(dp[left+1][right-1], dp[left+2, right]) 오른쪽에 있는 dp[left][right]=piles[right]+max([dpleft]+1], [right-1], [right-1], [right-right]를 가져가면 [right],좌우에서 가장 큰 것을 선택하십시오: dp[left][right]=max(piles[left]+max(dp[left+1][right-1]dp[left+2,right]),piles[right]+max(dp[left+1][right-1],dp[left,right-2]).

class Solution {
public:
    using VV=vector<vector<int> >;
    using V=vector<int>;
    bool stoneGame(vector<int>& piles) {
        int n=piles.size();
        vector<vector<int> > dp(n,vector<int>(n,-1));
        vector<int> alex(n,0);//   alex   pile       piles    alexsum
        int alexsum=maxsum(dp,alex,piles,0,n-1);
        int leesum=0;//           piles    alexsum  
        for(int i=0;i<n;++i){
            if(!alex[i]){
                leesum+=piles[i];
            }
        }
        //cout<
        if(alexsum>leesum){
            return true;
        }else{
            return false;
        }
    }
    int maxsum(VV& dp,V& alex,V& piles,int left,int right){
        if(left>right)
            return 0;
        if(dp[left][right]!=-1)
            return dp[left][right];
        int choosel=piles[left]+max(maxsum(dp,alex,piles,left+1,right-1),maxsum(dp,alex,piles,left+2,right));
        int chooser=piles[right]+max(maxsum(dp,alex,piles,left+1,right-1),maxsum(dp,alex,piles,left,right-2));
        if(choosel>chooser){
            alex[left]=1;
            dp[left][right]=choosel;
        }else{
            dp[left][right]=chooser;
            alex[right]=1;
        }
        //cout<
        return dp[left][right];
    }
};