2019-09-07 16:34:48
- 877. Stone Game
问题描述：
问题求解：
典型的博弈问题，也是一个典型的min-max问题。通常使用算diff的方法把min-max转为求max。
dp[i][j] : i ~ j 玩家 A 和 玩家 B 得分的diff。
public boolean stoneGame(int[] piles) {
int n = piles.length;
int[][] dp = new int[n][n];
return helper(piles, 0, n - 1, dp) > 0;
}
private int helper(int[] piles, int begin, int end, int[][] dp) {
if (dp[begin][end] != 0) return dp[begin][end];
if (begin == end) return dp[begin][end] = piles[begin];
return dp[begin][end] = Math.max(piles[begin] - helper(piles, begin + 1, end, dp), piles[end] - helper(piles, begin, end - 1, dp));
}
- 1140. Stone Game II
问题描述：
问题求解：
public int stoneGameII(int[] piles) {
int n = piles.length;
int[][] dp = new int[n][n];
return (sum(piles, 0, n - 1) + helper(piles, 0, 1, dp, n)) / 2;
}
private int helper(int[] piles, int s, int m, int[][] dp, int n) {
if (dp[s][m] != 0) return dp[s][m];
if (n - s <= 2 * m) return dp[s][m] = sum(piles, s, n - 1);
int best = Integer.MIN_VALUE;
int curSum = 0;
for (int i = 1; i <= 2 * m; i++) {
curSum += piles[s + i - 1];
best = Math.max(best, curSum - helper(piles, s + i, Math.max(i, m), dp, n));
}
return dp[s][m] = best;
}
private int sum(int[] nums, int l, int r) {
int res = 0;
for (int i = l; i <= r; i++) {
res += nums[i];
}
return res;
}