纸牌博弈问题：范围尝试模型

给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌 规定玩家A先拿，玩家B后拿 但是每个玩家每次只能拿走最左或者最右纸牌 玩家A和玩家B都是绝顶聪明 请返回最后获胜者的分数

方法1： 暴力递归法

  1. /**
  2.  * 方式1： 暴力递归方法
  3.  * @param arr
  4.  * @return
  5.  */
  6. // 根据规则，返回获胜者的分数
  7. public static int win1(int[] arr) {
  8.     if (arr == null || arr.length == 0) {
  9.         return 0;
  10.     }
  11.     // 先手得分
  12.     int first = f1(arr, 0, arr.length - 1);
  13.     // 后手得分
  14.     int second = g1(arr, 0, arr.length - 1);
  15.     return Math.max(first, second);
  16. }
  18. //先手函数 在数组arr[L..R]上，先手获得的最好分数返回
  19. public static int f1(int[] arr, int L, int R) {
  20.     if (L == R) {
  21.         return arr[L];
  22.     }
  23.     int p1 = arr[L] + g1(arr, L + 1, R);
  24.     int p2 = arr[R] + g1(arr, L, R - 1);
  25.     return Math.max(p1, p2);
  26. }
  28. //后手函数 arr[L..R]，后手获得的最好分数返回
  29. public static int g1(int[] arr, int L, int R) {
  30.     if (L == R) {
  31.         return 0;
  32.     }
  33.     int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
  34.     int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
  35.     return Math.min(p1, p2);  // 没有选择权
  36. }

方法2： 缓存法

/**
 * 方法二：傻缓存方法
 */
public static int win2(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] fmap = new int[N][N];
    int[][] gmap = new int[N][N];

    // 初始化，-1表示没计算过
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            fmap[i][j] = -1;
            gmap[i][j] = -1;
        }
    }

    // 原始的递归函数，参数带两个缓存表
    int first = f2(arr, 0, arr.length - 1, fmap, gmap);
    int second = g2(arr, 0, arr.length - 1, fmap, gmap);

    return Math.max(first, second);
}

// arr[L..R]，先手获得的最好分数返回
public static int f2(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] + g2(arr, L + 1, R, fmap, gmap);
        int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
        ans = Math.max(p1, p2);
    }
    fmap[L][R] = ans;
    return ans;
}

// // arr[L..R]，后手获得的最好分数返回
public static int g2(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 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
        int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
        ans = Math.min(p1, p2);
    }
    gmap[L][R] = ans;
    return ans;
}

方法3： 动态规划法

/**
 * 方式三： 动态规划
 */
public static int win3(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] fmap = new int[N][N];
    int[][] gmap = new int[N][N];
    for (int i = 0; i < N; i++) {
        // f对角线的值为arr[i]
        fmap[i][i] = arr[i];
    }

    // 按照对角线推
    for (int startCol = 1; startCol < N; startCol++) {
        int L = 0;
        int R = startCol;
        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++;
        }
    }
    return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
}