掬水月在手
弄花香满衣
先是一波暴力深搜，然后再套记忆化搜索。
暴力思路：递归，每个子问题都是求解出在当前区间内如果先手能取得的最大和，最后的边界就是left == right。
class Solution {
private:
int dfs(vector<int>& nums, int left, int right, vector<int> &pre_sum) {
if (left == right) return nums[left];
int right_s = dfs(nums, left + 1, right, pre_sum);
int left_s = dfs(nums, left, right - 1, pre_sum);
return max(nums[left] + (pre_sum[right + 1] - pre_sum[left + 1] - right_s),
nums[right] + (pre_sum[right] - pre_sum[left] - left_s));
}
public:
bool PredictTheWinner(vector<int>& nums) {
vector<int> pre_sum(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++)
pre_sum[i + 1] = pre_sum[i] + nums[i];
int ret = dfs(nums, 0, nums.size() - 1, pre_sum);
return ret * 2 >= pre_sum[nums.size()];
}
};
为了避免重复计算进行加速，直接用二维数组缓存每次递归计算的结果。。。
class Solution {
private:
int dfs(vector<int>& nums, int left, int right, vector<int> &pre_sum, vector<vector<int>> &dp) {
if (dp[left][right] != -1) return dp[left][right];
if (left == right) return nums[left];
int right_s = dfs(nums, left + 1, right, pre_sum, dp);
int left_s = dfs(nums, left, right - 1, pre_sum, dp);
return dp[left][right] = max(nums[left] + (pre_sum[right + 1] - pre_sum[left + 1] - right_s),
nums[right] + (pre_sum[right] - pre_sum[left] - left_s));
}
public:
bool PredictTheWinner(vector<int>& nums) {
vector<int> pre_sum(nums.size() + 1, 0);
vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), -1));
for (int i = 0; i < nums.size(); i++)
pre_sum[i + 1] = pre_sum[i] + nums[i];
int ret = dfs(nums, 0, nums.size() - 1, pre_sum, dp);
return ret * 2 >= pre_sum[nums.size()];
}
};
