leetcode 486. Predict the Winner

leetcode 486. Predict the Winner

class Solution {public:bool predictTheWinner(vector<int>& nums) {int m = nums.size();// f[i][j]表示(i,j)区间上，先手能超过后手多少分std::vector<std::vector<int>> f(m, std::vector<int>(m));for (int i = 0; i < m; i++) f[i][i] = nums[i];for (int len = 2; len <= m; len++)for (int i = 0; i + len - 1 < m; i++) {int j = i + len - 1;f[i][j] = max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);}return f[0][m - 1] >= 0;}
};

可以记录每个状态是怎么转移过来的，然后reverse一下，就得到最优方案了