Two Players Fetch Number -- dp

Question:

 给一个数组，A, B轮流从头尾处选出一个数字，求当B使用:

 * 1）贪心

 * 2）最优策略时，

 * A能取到所有数字之和最大。

Answer:

1. Player B uses greedy method to fetch number:

Example: B采用的是GREEDY方法

* 也就是B一定是取头、尾里面最大的那一个。 问A能取到的最大值。比如说2 4 7 3，A可以先取3， B肯定取7，A再取4，B取2，

* 这样A取到的和是7。 另外就是A先取2， B只能在3和4里面选 B因为是GREEDY 所以肯定选4， 那么A就能取7，这样A取到的和是9。

* 9>7所以返回9. 假定unique.

public int maxPick(int[] nums) {

if (nums == null || nums.length == 0)

throw new IllegalArgumentException("Empty array is not valid.");

int n = nums.length;

int[][] dp = new int[n][n];

for (int k = 2; k <= n; k += 2) {

for (int i = 0; i <= n - k; i++) {

int j = i + k - 1;

                                //edge case

if (k == 2) {

dp[i][j] = Math.max(nums[i], nums[j]);

continue;

}

                                //DP general case

int res1 = nums[i];

int res2 = nums[j];

// for res1, A fetches left element nums[i] firstly!

if (nums[i + 1] > nums[j]) {

res1 += dp[i + 2][j];

} else {

res1 += dp[i + 1][j - 1];

}

// for res2, A fetches right element nums[j] firstly!

if (nums[i] > nums[j - 1]) {

res2 += dp[i + 1][j - 1];

} else {

res2 += dp[i][j - 2];

}

dp[i][j] = Math.max(res1, res2);

}

}

return dp[0][n - 1];

}

2. Player B uses same optimized strategy like Player A to fetch number:
// 2. DP: dp[i,j] = max(v[i] + min (dp[i+2,j], dp[i+1,j-1]), v[j] + min(dp[i,j-2], dp[i+1,j-1]));
//Example: [2 4 7 3]
//2+7 = 9, selected!
//3+4 = 7

public int maxPick(int[] nums) {
if (nums == null || nums.length == 0)
throw new IllegalArgumentException("Empty array is not valid.");

int n = nums.length;
int[][] dp = new int[n][n];

for (int k = 2; k <= n; k += 2) {
for (int i = 0; i <= n - k; i++) {
int j = i + k - 1;
//edge case!
if (k == 2) {
dp[i][j] = Math.max(nums[i], nums[j]);
continue;
}
int res1 = nums[i];
int res2 = nums[j];
// for res1, A fetches nums[i] firstly
res1 += Math.min(dp[i+2][j], dp[i+1][j-1]);
// for res2, A fetches nums[j] firstly
res2 += Math.min(dp[i][j-2], dp[i+1][j-1]);
dp[i][j] = Math.max(res1, res2);
}
}
            return dp[0][n - 1];

}