预测赢家-动态规划法

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

假设每个玩家的玩法都会使他的分数最大化，输出赢家分数。

int win(vector<int>& vec){//返回获胜者分数
    int n = vec.size();
    vector<vector<int>>fdp(n,vector<int>(n,0));
    vector<vector<int>>gdp(n,vector<int>(n,0));
    
    for(int i = 0;i<n;i++){
        fdp[i][i] = vec[i]; //先手
        gdp[i][i] = 0; //后手
    }
   //对角线依赖
    for(int startcol = 1;startcol <n;startcol ++){
        int l = 0;
        int r = startcol;
        while(r<n){
            fdp[l][r] = max(gdp[l+1][r]+vec[l] ,gdp[l][r-1] + vec[r]);
            gdp[l][r] = min(fdp[l+1][r],fdp[l][r-1]);
            l++;
            r++;
        }
    }
    return max(fdp[0][n-1], gdp[0][n-1]);
}

int main(){
    vector<int>vec{1,100,4,4,5};
    cout<<win1(vec)<<endl;
    return 0;
}

作者：想玩飞盘的山羊拥抱太阳

链接：https://www.nowcoder.com/discuss/659508294435799040?sourceSSR=users

来源：牛客网