排成一条线的纸牌博弈问题

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strCards = br.readLine().split(" ");
        int[] cards = new int[n];
        for(int i = 0; i < n; i++) cards[i] = Integer.parseInt(strCards[i]);
        System.out.println(first(cards, 0, cards.length - 1));     // 假设A玩家先，并让他获胜
    }
    
    // 先手函数
    private static int first(int[] cards, int left, int right) {
        if(left == right) return cards[left];      // 剩最后一张牌，拿走
        // 先手利益最大化
        return Math.max(cards[left] + second(cards, left + 1, right), cards[right] + second(cards, left, right - 1));
    }
    
    // 后手函数
    private static int second(int[] cards, int left, int right) {
        if(left == right) return 0;      // 剩最后一张牌，被先手的拿了
        return Math.min(first(cards, left + 1, right), first(cards, left, right - 1));    // 先手留最少的给后手
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strCards = br.readLine().split(" ");
        int[] cards = new int[n];
        for(int i = 0; i < n; i++) cards[i] = Integer.parseInt(strCards[i]);
        // 先手和后手一起动规
        int[][] dpFirst = new int[n][n];
        int[][] dpSecond = new int[n][n];
        for(int right = 0; right < n; right ++){
            for(int left = right; left >= 0; left --){
                if(left == right){
                    // 只剩一张牌，先手的拿
                    dpFirst[left][right] = cards[left];
                    dpSecond[left][right] = 0;
                }else if(left < right){
                    dpFirst[left][right] = Math.max(cards[left] + dpSecond[left + 1][right], cards[right] + dpSecond[left][right - 1]);
                    dpSecond[left][right] = Math.min(dpFirst[left + 1][right], dpFirst[left][right - 1]);
                }
            }
        }
        System.out.println(Math.max(dpFirst[0][n - 1], dpSecond[0][n - 1]));
    }
}

//一般的递归法和动态规划方法，左神的书已经讲的比较清楚
//这里主要说一说另一种思路
//设胜者的总分为x,败者的总分为y，且有 x - y = diff; //方程一
//又因为两者的分数和为纸牌的总分，则有 x + y = sum; //方程二
//联立方程式可得 x = (sum + diff)/2;
//因此题目就转化为求两者的总分差diff
//令递推公式f(i,j):在剩余的i~j牌中,A(先拿)的分数减去B(后拿)的分数
//因此 f(i,j)=max(arr[i]-f(i+1,j),arr[j]-f(i,j-1));
//上式中的f(i+1,j)为剩余牌中B的分数减去A的分数,加负号并加上arr[i],
//代表A取最左边牌的情况，arr[j]-f(i,j-1)的含义为取最右的情况

//根据递推公式直接递归的方法
//diff = first - second
int getDiffCore(const int *arr, int i, int j);

int winner_Solution3_Recursive(const int arr[], const int len)
{
	if (arr == NULL || len < 1)
		return 0;

	int sum = 0;
	for (int i = 0; i < len; ++i)
		sum += arr[i];

	int diff = getDiffCore(arr, 0, len - 1);
	if (diff < 0)
		diff = -diff;

	return (sum + diff) / 2;
}

int getDiffCore(const int *arr, int i, int j)
{
	if (i == j)
		return arr[i];

	return std::max(arr[i] - getDiffCore(arr, i + 1, j), arr[j] - getDiffCore(arr, i, j - 1));
}


//===================================
//一般的动态规划
int winner_Solution3(const int arr[], const int len)
{
	if (arr == NULL || len < 1)
		return 0;

	int sum = 0;
	for (int i = 0; i < len; ++i)
		sum += arr[i];

	int **f = make2DArray<int>(len, len);
	for (int j = 0; j < len; ++j)
	{
		f[j][j] = arr[j];
		for (int i = j - 1; i >= 0; --i)
		{
			f[i][j] = std::max(arr[i] - f[i + 1][j], arr[j] - f[i][j - 1]);
		}
	}

	int diff = f[0][len - 1];
	if (diff < 0)
		diff = -diff;

	return (sum + diff) / 2;
}



//================================
//空间压缩后，空间复杂度为O(N)
int winner_Solution3(const int arr[], const int len)
{
	if (arr == NULL || len < 1)
		return 0;

	int sum = 0;
	for (int i = 0; i < len; ++i)
		sum += arr[i];

	int *dp = new int[len];
	for (int i = len - 1; i >= 0; --i)
	{
		dp[i] = arr[i];
		for (int j = i + 1; j < len; ++j)
		{
			dp[j] = std::max(arr[i] - dp[j], arr[j] - dp[j - 1]);
		}
	}

	int diff = dp[len - 1];
	if (diff < 0)
		diff = -diff;

	
	return (sum + diff) / 2;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = a[i];
            s[i][i] = 0;
        }
        for (int d = 1; d < n; d++) {
            for (int i = 0; i < n - d; i++) {
                f[i][i + d] = Math.max(a[i] + s[i + 1][i + d], a[i + d] + s[i][i + d - 1]);
                s[i][i + d] = Math.min(f[i + 1][i + d], f[i][i + d -1]);
            }
        }
        System.out.println(Math.max(f[0][n-1], s[0][n-1]));
    }
}