排成一条线的纸牌博弈问题

#include <vector>
#include <iostream>
using namespace std;
int win1(vector<int>& arr) {//使用标准二维dp
    int n = arr.size();
    vector<vector<int>> first(n, vector<int>(n, 0)); //first[i][j]表示在arr[i...j]上先手获得的最好分数
    vector<vector<int>> second(n, vector<int>(n, 0)); //second[i][j]表示在arr[i...j]上后手获得的最好分数
    for(int i = 0; i < n; i++) {
        first[i][i] = arr[i];
        for(int j = i-1; j >=0; j--) {
            //先手要么取左边的arr[j]，要么取右边的aar[i]，趣时主要考虑自己作为后手在剩下的局面上能拿多少分
            first[j][i] = max(arr[j] + second[j+1][i], arr[i] + second[j][i-1]);
            //这句我花了很大心思理解，为什么是min？因为后手是被动的，只能挑先手剩下的最坏情况
            second[j][i] = min(first[j+1][i], first[j][i-1]);
        }
    }
    return max(first[0][n-1], second[0][n-1]);
}

//参考：https://www.nowcoder.com/questionTerminal/19c98d950b3347d19f991d10bde12288?toCommentId=5976617
int win2(vector<int>& arr) {//使用滚动数组，压缩空间复杂度到O(n)
    int n = arr.size();
    vector<int> first(n, 0);
    vector<int> second(n, 0);
    for(int i = 0; i < n; i++) {
        first[i] = arr[i]; //first[i][i]
        second[i] = 0; // second[i][i] 很重要，一维时需要重置，容易遗漏
        for(int j = i - 1; j >= 0; j--) {
            int tmp = first[j]; //first[j][i-1]，需要保存，因为一维时first[j]会覆盖它
            first[j] = max(arr[j] + second[j+1], arr[i] + second[j]);
            second[j] = min(first[j+1], tmp);
        }
    }
    return max(first[0], second[0]);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    //cout << win1(arr) << endl;
    cout << win2(arr) << endl;
    return 0;
}