Predict the Winner
给一个数组, 两个人只能从两端取数, 求预测那个人能赢. 我就是dfs直接做的, 不过时间太大了. 我看到答案用的是贪婪算法, 选的人肯定选start和end中相对大的, 但是找到这个大的, 需要通过dfs.
public class Solution {
public boolean PredictTheWinner(int[] nums) {
return helper(nums, 0, nums.length-1)>=0;
}
private int helper(int[] nums, int s, int e){
return s==e ? nums[s] : Math.max(nums[e] - helper(nums, s, e-1), nums[s] - helper(nums, s+1, e));
}
}