``````class Solution {
int maxScore(int[] cards) {
int n = cards.length;
int[][] dp = new int[2][n + 1];
int sum = 0;
int A, B;
A = 0; B = 1;

for (int i = 1; i <= n; i++) {
// sum is the score sum of left i cards
sum += cards[n - i];

for (int j = 0; j < 2; j++) {
int min = Integer.MAX_VALUE;
if (i >= 3) min = Math.min(min, dp[B][i - 3]);
if (i >= 2) min = Math.min(min, dp[B][i - 2]);
if (i >= 1) min = Math.min(min, dp[B][i - 1]);
dp[A][i] = sum - min;

A = (A + 1) % 2;
B = (B + 1) % 2;
}

}

return dp[0][n];
}
}
``````

``````class Solution {
int maxScore(int[] cards) {
int n = cards.length;
int[] dp = new int[n + 1];
int sum = 0;

for (int i = 1; i <= n; i++) {
sum += cards[n - i];

int min = Integer.MAX_VALUE;
if (i >= 3) min = Math.min(min, dp[i - 3]);
if (i >= 2) min = Math.min(min, dp[i - 2]);
if (i >= 1) min = Math.min(min, dp[i - 1]);

dp[i] = sum - min;
}

return dp[n];
}
}
``````

``````class Solution {
int maxScore(int[] cards) {
int n = cards.length;
int p, q, r, sum;

p = q = Integer.MAX_VALUE;

// init when no card
r = sum = 0;

for (int i = 1; i <= n; i++) {
sum += cards[n - i];

int min = Math.min(Math.min(p, q), r);
p = q;
q = r;
r = sum - min;
}

return r;
}
}
``````

[Java] 纯文本查看 复制代码
public int findMaxScore(int[] cards) {
int[] memo = new int[cards.length];
int sum = 0;
for (int card: cards) sum += card;
return (sum + helper(cards, 0, memo)) / 2;
}

``````public int helper(int[] cards, int cur, int[] memo) {
if (cur == cards.length - 1) return cards[cur];
if (cur == cards.length - 2) return Math.max(cards[cur] - cards[cur + 1], cards[cur] + cards[cur + 1]);
if (cur == cards.length - 3) {
int valOne = cards[cur] - Math.max(cards[cur + 1] - cards[cur + 2], cards[cur + 1] + cards[cur + 2]);
int valTwo = cards[cur] + cards[cur + 1] - cards[cur + 2];
int valThree = cards[cur] + cards[cur + 1] + cards[cur + 2];
return Math.max(valOne, Math.max(valTwo, valThree));
}
if (memo[cur] > 0) return memo[cur];
int oneCardValue = cards[cur] - helper(cards, cur + 1, memo);
int twoCardValue = cards[cur] + cards[cur + 1] - helper(cards, cur + 2, memo);
int threeCardValue = cards[cur] + cards[cur + 1] + cards[cur + 2] - helper(cards, cur + 3, memo);
memo[cur] = Math.max(oneCardValue, Math.max(twoCardValue, threeCardValue));
return memo[cur];
}``````

[C++] 纯文本查看 复制代码#include

bool solution(vectornums)
{
int N = nums.size();
vectorsum(N+1);
sum[N] = 0;
for (int i=N-1; i>=0; i–)
sum[i] = sum[i+1]+nums[i];

``````vector<int>dp(N+1,0);
dp[N-1]=sum[N-1];
dp[N-2]=max(sum[N-2],nums[N-2]);

for (int i=N-3; i>=0; i--)
{
int scoreA = nums[i]+sum[i+1]-dp[i+1];
int scoreB = nums[i]+nums[i+1]+sum[i+2]-dp[i+2];
int scoreC = nums[i]+nums[i+1]+nums[i+2]+sum[i+3]-dp[i+3];
dp[i] = max(scoreA,scoreB);
dp[i] = max(dp[i],scoreC);
}
return dp[0]>=sum[0]-dp[0];
``````

}

int main()
{
vectornums({1,2,-3,8});
cout<<solution(nums)<<endl;
}

``````class Solution {
int maxScore(int[] cards) {
int n = cards.length;
int[][] dp = new int[2][n + 1];
int sum = 0;
int A, B;
A = 0; B = 1;

for (int i = 1; i <= n; i++) {
// sum is the score sum of left i cards
sum += cards[n - i];

for (int j = 0; j < 2; j++) {
int min = Integer.MAX_VALUE;
if (i >= 3) min = Math.min(min, dp[B][i - 3]);
if (i >= 2) min = Math.min(min, dp[B][i - 2]);
if (i >= 1) min = Math.min(min, dp[B][i - 1]);
dp[A][i] = sum - min;

A = (A + 1) % 2;
B = (B + 1) % 2;
}

}

return dp[0][n];
}
}
``````

``````class Solution {
int maxScore(int[] cards) {
int n = cards.length;
int[] dp = new int[n + 1];
int sum = 0;

for (int i = 1; i <= n; i++) {
sum += cards[n - i];

int min = Integer.MAX_VALUE;
if (i >= 3) min = Math.min(min, dp[i - 3]);
if (i >= 2) min = Math.min(min, dp[i - 2]);
if (i >= 1) min = Math.min(min, dp[i - 1]);

dp[i] = sum - min;
}

return dp[n];
}
}
``````

``````class Solution {
int maxScore(int[] cards) {
int n = cards.length;
int p, q, r, sum;

p = q = Integer.MAX_VALUE;

// init when no card
r = sum = 0;

for (int i = 1; i <= n; i++) {
sum += cards[n - i];

int min = Math.min(Math.min(p, q), r);
p = q;
q = r;
r = sum - min;
}

return r;
}
}
``````

LC 464
LC 486
LC 877

dp[i][j] = max(拿一张， 拿二张， 拿三张)

leetcode上有个很类似的题是每次从两头拿看谁能赢