题目

A和B轮流从一个数组左右两端取数，A先B后，每次取一个数，最终取数总和大者获胜，两人每次都会选择最有利的策略，求获胜者取数的和。

思路

笔试时遇到的一道算法题，也是博弈论中非常经典的入门题目了。从先后手的角度考虑，先手在行动一次后获得左右两端数中的一个，然后转换为后手；而后手在先手取完一个数之后，转换为先手。两人每次都会选择最有力的策略，因此先手变为后手后采取的策略与后手相同，反之亦然。先手一定会采取使得自己分数最大的行动，同时迫使后手拿到其进入先手后能拿到的最小分数。这是本题中的先手优势。
采用递归的方法，先手函数first()返回先手能拿到的最大分数，后手函数second()返回后手能拿到的最大分数，两者相互调用。
时间复杂度O(\(2^n\))，空间复杂度O(n)。

代码

class Solution {
public:
    int win(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        // 返回先手和后手分数更大的值
        return max(first(nums, 0, n - 1), second(nums, 0, n - 1));
    }

    int first(vector<int>& nums, int i, int j) {
        if (i == j) {
            // 只剩一个数时，先手会拿走这个数
            return nums[i];
        }
        // 拿走左右两端中一个数后，采取后手策略
        return max(nums[i] + second(nums, i + 1, j), nums[j] + second(nums, i, j - 1));
    }

    int second(vector<int>& nums, int i, int j) {
        if (i == j) {
            // 只剩一个数时，后手拿不到数，返回0
            return 0;
        }
        // 先手拿走两端一个数后，后手采取先手策略，先手一定会保证后手只能拿到两种情况下更小的那种
        return min(first(nums, i + 1, j), first(nums, i, j - 1));
    }
};

改进

可以用动态规划替代递归，降低时间复杂度。定义两个二维数组f[n][n]和s[n][n]，f[i][j]表示先手取i到j范围的最大值，s[i][j]表示后手取i到j范围的最大值。从内往外迭代。
时间复杂度O(\(n^2\))，空间复杂度O(\(n^2\))。

代码

class Solution {
public:
    int win(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<vector<int>> f(n, vector<int>(n, 0));
        vector<vector<int>> s(n, vector<int>(n, 0));
        
        for (int i = 0; i < n; ++i) {
            f[i][i] = nums[i];
        }

        for (int i = 1; i < n; ++i) {
            for (int L = 0, R = i; R < n; ++L, ++R) {
                f[L][R] = max(nums[L] + s[L + 1][R], nums[R] + s[L][R - 1]);
                s[L][R] = min(f[L + 1][R], f[L][R - 1]);
            }
        }

        return max(f[0][n - 1], s[0][n - 1]);
    }
};