P40-预测赢家-动态规划

//预测赢家
/*
 * 给定一个表示分数的非负整数数组。玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，
 * 然后玩家1拿，......。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。
 * 最终获得分数总和最多的玩家获胜
 * 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
 *
 * 扩展：石子游戏
 * */
public class P40 {
    public static void main(String[] args) {

//        int[] arr = new int[]{5,200,2,3};    //扩展知识：当数量是偶数的时候，先手是会存在必赢策略的（大于等于后手）
        int[] arr = new int[]{5,200,2,3,5};
        System.out.println(maxScore(arr,0, arr.length-1));
        System.out.println(dp(arr));
        System.out.println(dp2(arr));
    }

    //递归
    //递归出口 只有一个元素或两个元素，返回最大的值，之后的都是通过max来判断
    //p1 max(fun(l), fun(r))
    //p2 max(fun(l), fun(r))
    //max(p1, p2)

    //l是左指针，r是右指针
    /*
     * 公式计算
     * 假设p1取l，p2剩下l+1和r可以取，
     *       假设p2取l+1，p1剩下l+2和r可以取
     *       假设p2取r，p1剩下l+1和r-1可以取
     *           之后p2怎么取，都是这两个公式 {l+2和r}、{l+1和r-1} （前提是l和r要重新指向）
     *           但p2是聪明的，假设{l+2和r}能让p1更大时，p2就会取r，导致你只能在{l+1和r-1}中取，让你处于不利状态
     * 假设p1取r，p2剩下l和r-1可以取
     *       假设p2取l，p1剩下l+1和r-1可以取
     *       假设p2取r-1，p1剩下l和r-2可以取
     *           之后p2怎么取，都是这两个公式 {l+1和r-1}、{l和r-2} （前提是l和r要重新指向）
     *
     * */
    public static int maxScore(int[] arr, int l, int r) {
        if (l == r) {       //如果只剩一个元素，只能选择它了
            return arr[l];
        }

        //假设先手去左边元素，这个时候后手就会获取{l+1,r}的最大值
        //然后判断 先手的数 - 后手的数
        //因为是递归，最终公式变为 p1 - (p2 - (p1 - (p2 - p1)))     //假设5个元素的就是这样，一直递归
        // p1 - p2 + p1 - p2 + p1，就得到p1取左边的数时，能否比p2的值大
        int left = arr[l] - maxScore(arr, l+1, r);
        //右边同理
        int right = arr[r] - maxScore(arr, l, r-1);

        return Math.max(left, right);   //结果大于0就是赢，小于0就是输
    }

    //更一步优化，动态规划
    //上方两个maxScore调用，假如结果是left，相当于right白计算
    /*
    * maxScore(arr, l+1, r)存储到 二维数组[i][j]
    * 往左移，i+1，往右移 j-1，叫做dp数组
    * 初始化：
    * if (l == r) {       //如果只剩一个元素，只能选择它了
          return arr[l];
      }
    * */
    public static boolean dp(int[] arr){
        int length = arr.length;
        int[][] dp = new int[length][length];

        //初始化
        for(int i=0; i<length; i++){
            dp[i][i] = arr[i];
        }


        //最大范围去到长度-2，因为假设一直都是取左边的数，最后剩下2个数的时候，i=length-2，已经知道结果了
        for(int i=length-2; i>=0; i--){
            for(int j=i+1; j<length; j++){
                dp[i][j] = Math.max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1]);
                /*
                 * 来自上方的公式
                 * arr[l] - maxScore(arr, l+1, r) ==> arr[i] - dp[i+1][j]
                 * arr[r] - maxScore(arr, l, r-1) ==> arr[j] - dp[i][j-1]
                 * 相当于把递归的结果保存起来
                 * */
            }
        }

        //i的位置到j的位置，先手与后手的差值
        return dp[0][length-1] >= 0;
    }

    //可以使用一维数组优化
    /*
     * arr[l]-maxScore(arr, l+1, r) ==> arr[i]-dp[i+1][j] ==> arr[i]-dp[j][j] ==> arr[i]-arr[j]
     * arr[r]-maxScore(arr, l, r-1) ==> arr[j]-dp[i][j-1] ==> arr[j]-dp[j-1][j-1] ==> arr[j]-arr[j-1]
     * */
    public static boolean dp2(int[] arr){
        int length = arr.length;
        int[] dp = new int[length];

        //初始化
        for(int i=0; i<length; i++){
            dp[i] = arr[i];
        }


        //最大范围去到长度-2，因为假设一直都是取左边的数，最后剩下2个数的时候，i=length-2，已经知道结果了
        for(int i=length-2; i>=0; i--){
            for(int j=i+1; j<length; j++){
                dp[j] = Math.max(arr[i] - dp[j], arr[j] - dp[j-1]);

            }
        }

        //i的位置到j的位置，先手与后手的差值
        return dp[length-1] >= 0;
    }

}