Question
Solution
题目大意：
说有偶数个数字，alex和lee两个人比赛，每次轮流从第一个数字或最后一个数字中拿走一个（偶数个数字，所以他俩拿的数字个数相同），最后比谁拿的数字总和大。题目是让我们设计一个算法，对于任意给定的一系列数字，判断如果alex先选，是否一定赢（所有数加起来是奇数，所以不存在平局）？
思路：
朴素的暴力递归所有可能的走法，回归的时候只贪心地保留更优的那个解就可以了。然后对于可能的重复的子问题，用一个表储存之前所有解决过的子问题解（动态规划）就可以避免指数级增长的复杂度。
Java实现：
public boolean stoneGame(int[] piles) {
return true;
}
动态规划实现：
class Solution {
public boolean stoneGame(int[] piles) {
p = piles;
int len = piles.length;
dp = new int[len][len];
return dp(0,len-1) > 0;
}
private int[] p; //copy of piles
private int[][] dp; //solved subproblems
private int dp(int lo, int hi) {
if (lo == hi) {
return 0;
}
if (dp[lo][hi] != 0) {
return dp[lo][hi];
}
int res = 0;
if ((hi - lo + 1) % 2 == 0) {
res = Math.max(dp(lo+1,hi) + p[lo], dp(lo,hi-1) + p[hi]);
} else {
res = Math.min(dp(lo+1,hi) - p[lo], dp(lo,hi-1) - p[hi]);
}
dp[lo][hi] = res;
return res;
}
}