90 排成一条线的纸牌博弈问题
Table of Contents

ac

递归法

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int ans = Math.max(f(arr, 0, n - 1), s(arr, 0, n - 1));
        System.out.println(ans);
    }

    static int f(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
    }

    static int s(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }

}
/*
4
1 2 100 4

101
 */

or

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        int sums = 0;
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            sums += arr[i];
        }
        int sumA = rev(arr, 0, n-1, true);
        System.out.println(Math.max(sumA, sums - sumA));
    }

    static int rev(int[] arr, int left, int right, boolean first) {
        if(left == right){
            if(first) {
                return arr[left];
            }
            return 0;
        }
        if(first) {
            int case1 = arr[left] + rev(arr, left + 1, right,false);
            int case2 = rev(arr, left, right-1,false) + arr[right];
            return Math.max(case1, case2);
        }else {
            int case1 = rev(arr, left + 1, right, true);
            int case2 = rev(arr, left, right-1, true);
            return Math.min(case1, case2);
        }
    }

}
/*
4
1 2 100 4

101

3
2 100 4

100
 */

动态规划

dp[i][j]表示arr[i...j](i <= j)下标间玩家1能够获得的分数减去玩家2能够获得的最大分数差，最后看dp[0][n-1]的正负来判断先手是否能赢

dp[i][i] = arr[i]
dp[i][i+1] = Math.abs(arr[i] - arr[i+1])
...

对于dp[i][j]

如果A选择了arr[j], 那么剩下 arr[i...j-1], 变成了dp[i][j-1]问题, 先手变成B

如果A选择了arr[i], 那么剩下 arr[i+1...j], 变成了dp[i+1][j]问题, 先手变成B

最后

eg:
dp[1][3] = Math.max(arr[3] - dp[1][2], arr[1] - dp[2][3])
dp[1][4] = Math.max(arr[4] - dp[1][3], arr[1] - dp[2][4])

5个数
0 1 2 3 4

求取
01 12 23 34
02 13 24
03 14
04

ac代码如下

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];

        int sums = 0; // 两数之和
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            sums += arr[i];
        }

        int[][] dp = new int[n][n];
        for(int i=0;i<n;i++) {
            dp[i][i] = arr[i];
        }
        for(int span=1;span<=n-1;span++){
            // 间距
            for(int index=0;index<n;index++){
               int i = index;
               int j = index + span;
               if(j >= n){
                   break;
               }
               if(i == j - 1){
                   dp[i][j] = Math.abs(arr[i] - arr[j]);
               }else {
                   dp[i][j] = Math.max(arr[j] - dp[i][j-1], arr[i] - dp[i+1][j]);
               }
            }
        }
        int cha = Math.abs(dp[0][n-1]); // 两数之差
        int ans = (sums + cha) / 2;
        System.out.println(ans);
    }

}
/*
4
1 2 100 4

101

3
2 100 4

100
 */