题目描述:
给你一个整数数组 nums
。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合,玩家 1 先手。开始时,两个玩家的初始分值都是 0
。每一回合,玩家从数组的任意一端取一个数字(即,nums[0]
或 nums[nums.length - 1]
),取到的数字将会从数组中移除(数组长度减 1
)。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时,游戏结束。
如果玩家 1 能成为赢家,返回 true
。如果两个玩家得分相等,同样认为玩家 1 是游戏的赢家,也返回 true
。你可以假设每个玩家的玩法都会使他的分数最大化。
数据范围:
$1\le nums.len \le 20; 0\le nums[i] \le 10^7$
题解:
博弈问题可以转化为有向图,两个人依次在图上行走,如果是一个有向无环图,可以通过遍历这张图得到答案。
如果状态非常多,可以使用dp记录答案,假设使用 $dp[i][j] = (first, second)$ 表示剩下的区间为 $[i, j]$ 时,先手和后手能得到的最大值。则很容易得到递推公式
其中,如果先手选择 $nums[i]$ 的话,那么下一次只能选择 $dp[i + 1][j]$ 的后手了;先手选择 $nums[j]$ 的话,下一次只能选择 $dp[i][j - 1]$ 的后手。
其中初始条件为 $dp[i][i]$ ,只有一个元素时,先手得到 $nums[i]$ ,后手得到 $0$ 。
遍历顺序:由于 $dp[i][j]$ 需要 $i + 1$ ,所以 $i$ 从大到小;同理 $j$ 从小到大。
由于 $dp[i][j]$ 只与 $dp[i + 1][j],dp[i][j-1]$ 有关,因此可以考虑一维优化,假设 $dp[i + 1]$ 这行已经算出来了,则 $dp[i + 1][j]$ 就是 $dp[j]$ , $dp[i][j-1]$ 就是 $dp[j-1]$ 。而且 $j$ 是从前往后更新的。因此可以直接在同一行更新。
也可以不使用先手后手空间。直接使用 $dp[i][j]$ 表示当前先手与后手的差值。则如果当前选择了 $nums[i]$ ,则后手得到的差值为 $dp[i + 1][j]$ 。假设先手为 $A$ ,后手为 $B$ ,则 $B-A = dp[i + 1][j]$ , $A-B = -dp[i + 1][j]$ ,因为在本回合 $A$ 取了 $nums[i]$ ,则 $dp[i][j] = \max(nums[i] - dp[i + 1][j],nums[j] - dp[i][j - 1])$ 。同样该方法也可以使用一维空间优化。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| auto optimize_cpp_stdio = []() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }(); class Solution { public: const static int maxn = 1e5 + 10; const static int maxm = 1e5 + 10; const int INF = 0x3f3f3f3f; bool predictTheWinner(vector<int> &nums) { int n = nums.size(); vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(n)); for (int i = 0; i < n; ++i) { dp[i][i].first = nums[i]; dp[i][i].second = 0; } for (int i = n - 2; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { int left = nums[i] + dp[i + 1][j].second; int right = nums[j] + dp[i][j - 1].second; if (left > right) { dp[i][j].first = left; dp[i][j].second = dp[i + 1][j].first; } else { dp[i][j].first = right; dp[i][j].second = dp[i][j - 1].first; } } } return dp[0][n - 1].first >= dp[0][n - 1].second; } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| auto optimize_cpp_stdio = []() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }(); class Solution { public: const static int maxn = 1e5 + 10; const static int maxm = 1e5 + 10; const int INF = 0x3f3f3f3f; bool predictTheWinner(vector<int> &nums) { int n = nums.size(); vector<int> dp(n); for (int i = 0; i < n; ++i) { dp[i] = nums[i]; }
for (int i = n - 2; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]); } } return dp[n - 1] >= 0; } };
|