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

暴力递归：对于一个玩家，有两种选择：先手或者后手；

分先手函数和后手函数；

import java.util.*;
import java.lang.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = scan.nextInt();
        }
        int A = f(arr, 0, N - 1);
        int B = g(arr, 0, N - 1);
        System.out.println(Math.max(A, B));
    }
    public static int f(int[] arr, int L, int R){
        if(L == R){//base case;
            return  arr[L];
        }
        //先手就可以选择拿左边或者右边，取最大的！
        int p1 = arr[L] + g(arr, L + 1, R);
        int p2 = arr[R] + g(arr, L, R - 1);
        return Math.max(p1, p2);
    }
    public static int g(int[] arr, int L, int R){
        if(L == R){
            return 0;
        }
        //后手的话就只能等对方先手后给自己留下最小的；
        int p1 = f(arr, L + 1, R);
        int p2 = f(arr, L, R - 1);
        return Math.min(p1, p2);
    }
}

自顶向下动态规划：加一个备忘录

import java.util.*;
import java.lang.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = scan.nextInt();
        }
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int A = f(arr, 0, N - 1, fmap, gmap);
        int B = g(arr, 0, N - 1, fmap, gmap);
        System.out.println(Math.max(A, B));
    }
    public static int f(int[] arr, int L, int R, int[][] fmap, int[][] gmap){
        if(fmap[L][R] != -1) return fmap[L][R];
        int ans = 0;
        if(L == R){
            ans =  arr[L];
        }else{
            int p1 = arr[L] + g(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + g(arr, L, R - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        fmap[L][R] = ans;
        return ans;
    }
    public static int g(int[] arr, int L, int R, int[][] fmap, int[][] gmap){
        if(gmap[L][R] != -1) return gmap[L][R];
        int ans = 0;
        if(L != R){
            int p1 = f(arr, L + 1, R, fmap, gmap);
            int p2 = f(arr, L, R - 1,  fmap, gmap);
            ans = Math.min(p1, p2);
        }
        gmap[L][R] = ans;
        return ans;
    }
}

终极版本，dp填表，动态规划！

import java.util.*;
import java.lang.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = scan.nextInt();
        }
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        //初始化
        for(int i = 0; i < N; i++){
                fmap[i][i] = arr[i];
        }
        for(int i = 1; i < N; i++){
            int L = 0;
            int R = i;
            while(R < N){
                //画图看转移方程，或者看递归过程依赖！
                fmap[L][R] = Math.max(arr[L] + gmap[L+1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                L++;
                R++;
            }
        }
        int A = fmap[0][N - 1];
        int B = gmap[0][N - 1];
        System.out.println(Math.max(A, B));
    }
}