题意

原题是力扣486.

类似于拿石子问题，两个人依次从石子堆中取走石子，最后获得石子数量最多的人获胜。

分析

本题一开始并没有想出来怎么做，不过可以发现，贪心显然是错误的策略，故而理论上是需要对所有的状态空间进行搜索的。不过题目的数据规模下，搜索并不是一个可行的解决方案，注意到我们实际上只关心当游戏进行到某一个状态时，当前某一方最优的局面（假设玩游戏的两方都是绝对聪明的），故而可以使用dp[i][j]表示当前取到下标i到j（包括两者）的石子时，最大的石子数量差值。

我觉得这个是比较难以想到的部分，不是记录某一方可以获得的最大值，而是记录一个相对值。好处就是状态转移十分自然。

那么在扩张到i, j这样的区间上时，应该是从i+1,j或i, j-1两个状态上进行转移，dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-piles[i][j-1])。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
    
        for(int len = 1;len<=nums.size();len++){
            for(int i = 0;i+len-1<nums.size();i++){
                int j = i+len-1;
                if(i==j){
                    dp[i][j] = nums[i];
                }else{
                    dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]);
                }
            }
        }

        return dp[0][nums.size()-1]>=0;
    }
};