随笔记录

算法——拿纸牌，最大积分是多少

2022-3-2 diaba 算法

package com.jiucaiyuan.net.question;

/**
 * 拿纸牌，得到最大分数
 * 给定一个整形数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，
 * 规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或者最右侧的纸牌，玩家A和
 * 玩家B都是绝顶聪明。请返回最后胜利者的分数
 * <p>
 * Created by jiucaiyuan on 2022/3/2.
 */
public class CardsSelect {
    /**
     * 给一个纸牌，拿牌规则，从最左侧或者从最右侧拿牌，两个人轮流拿，能拿到最大积分数是多少
     *
     * @param arr
     * @return
     */
    public static int win(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //
        return Math.max(firstSelect(arr, 0, arr.length - 1), secondSelect(arr, 0, arr.length - 1));
    }

    /**
     * @param arr 纸牌
     * @param l   可选择最左侧纸牌
     * @param r   可选择最右侧纸牌
     * @return 拿走一张牌得到的最大分数
     */
    public static int firstSelect(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        //先拿要得到最大分数
        return Math.max(arr[l] + secondSelect(arr, l + 1, r), arr[r] + secondSelect(arr, l, r - 1));
    }

    /**
     * @param arr 纸牌
     * @param l   先手拿之前可选择最左侧纸牌
     * @param r   先手拿之前可选择最右侧纸牌
     * @return
     */
    private static int secondSelect(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        //先手会让我得到最少的分数
        return Math.min(firstSelect(arr, l + 1, r), firstSelect(arr, l, r - 1));
    }

    /**
     * 从递归中改进过来，动态规划版本
     * 
     * @param arr
     * @return
     */
    public static int dp(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        //对角线位置值可以根据数组中值固定得到，初始化到表中
        for (int i = 0; i < arr.length; i++) {
            f[i][i] = arr[i];
        }
        int row = 0;
        int col = 1;
        //对角线开始位置，row行 col列
        while (col < arr.length) {
            int i = row;
            int j = col;
            while (i < arr.length && j < arr.length) {
                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
                i++;
                j++;
            }
            col++;
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);

    }


    public static void main(String[] args) {
//        int[] arr = {1, 4, 100, 100, 8};
        int[] arr = {1, 8};
        System.out.println(win(arr) + "<------->" + dp(arr));
    }

}