LeetCode 1690.石遊びVII

LeetCode 1690.石遊びVII
石のゲームの中で、アリスとボブは交代で自分のラウンドを行って、アリスは先に始まります.
n個の石が一列に並んでいる.各プレイヤーのラウンドでは、行から一番左の石または一番右の石を除去し、その行の残りの石の値の和と等しい得点を得ることができます.石が除去できない場合、得点の高い者が勝つ.ボブは彼がいつもゲームに負けていることに気づいた(かわいそうなボブ、彼はいつも負けている)ので、得点の差を減らすことにした.アリスの目標は得点差を最大限に拡大することだ.整数配列stonesを与え、stones[i]は左からi番目の石の値を表し、アリスとボブが最適なレベルを発揮した場合、得点の差を返してください.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/stone-game-vii
例1:
入力:stones=[5,3,1,4,2]出力:6解釈:アリス除去2,得点5+3+1+4=13.游戏情况:アリス=13,ボブ=0,石子=[5,3,1,4].ボブは5を削除し、3+1+4=8の得点を得た.游戏情况:アリス=13,ボブ=8,石子=[3,1,4].アリスは3を外し、得点1+4=5.游戏情况:アリス=18,ボブ=8,石子=[1,4].ボブは1を削除し、4点を取った.游戏情况:アリス=18、ボブ=12、石子=[4].アリスは4を外し、得点は0だった.游戏情况:アリス=18、ボブ=12、石=[]得点差18-12=6.
例2:
入力:stones=[7,90,5,1100,10,10,2]出力:122
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/stone-game-vii著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題分析:記憶検索方式を採用し、再帰的に求める.dp[l][r]代表区間[l,r]内アリスがボブをリードする点数
コードは次のとおりです.

const int MAXN=1e3+50;
int dp[MAXN][MAXN];
class Solution {
     
public:
    int n;
    int dfs(int l,int r,int sum,vector<int>& stones){
     
        if(l>=r) return 0;
        if(dp[l][r]!=-1) return dp[l][r];
        int turn=n-(r-l+1);//              
        //                    
        int flag=(turn%2==0)? 1:-1;
        //lm                ，rm  
        int lm=flag*(sum-stones[l])+dfs(l+1,r,sum-stones[l],stones);
        int rm=flag*(sum-stones[r])+dfs(l,r-1,sum-stones[r],stones);
        //             ，        。         
        if(turn%2==0){
     
            dp[l][r]=max(lm,rm);
        }
        else{
     
            dp[l][r]=min(lm,rm);
        }
        return dp[l][r];
    }
    int stoneGameVII(vector<int>& stones) {
     
        n=stones.size();
        int sum=0;
        for(int& stone:stones)
          sum+=stone;
        for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
            dp[i][j]=-1;
        return dfs(0,n-1,sum,stones);
    }
};