leetcode877. 石子游戏(动态规划-java)_Java

石子游戏

leetcode877. 石子游戏
动态规划专题:

leetcode877. 石子游戏

题目描述

暴力递归

代码演示

public static boolean stonegame(int[] piles) {
        int f = f(piles,0,piles.length - 1);
        int g = g(piles,0,piles.length - 1);
        return f > g;
    }

    /**
     * 先手玩家 alice
     * @param piles
     * @param l 起始位置
     * @param r 结束位置
     * @return
     */
    public static int f(int[]piles,int l , int r){
        //base case  越界直接返回
        if (l > r){
            return 0;
        }
        //l == r 说明只剩一个位置,先手拿走
        if(l == r){
            return piles[l];
        }
        //两种情况 选择 l 或者选择r
        int p1 = piles[l] + g(piles,l + 1,r);
        int p2 = piles[r] + g(piles,l,r - 1);
        //取两种情况的最优解
        return math.max(p1,p2);
    }

    /**
     * 后手玩家 bob 
     * @param piles
     * @param l 开始位置
     * @param r 结束位置
     * @return
     */
    public static int g(int[]piles,int l,int r){
        //base case 越界或者只剩一个时,都是0,因为只剩一个也会被先手玩家拿走
        if(l >= r){
            return 0;
        }
        //先手拿走 l 时
        int p1 = f(piles,l + 1,r);
        //先手拿走 r 时
        int p2 = f(piles,l,r - 1);
        //先手会选择最优解拿,所以会给剩下次优解.返回两者中的次优解
        return math.min(p1,p2);
    }

动态规划

    /**
     * 动态规划
     * @param piles
     * @return
     */
    public static boolean dp(int[] piles){
        int n = piles.length;
        //先手
        int[][]dp1 = new int[n][n];
        //后手
        int[][]dp2 = new int[n][n];

        for (int i = 0; i < n ; i++){
            dp1[i][i] = piles[i];
            int r = i;
            int l = 0;
            while (r < n){
                int p1 = piles[l] + dp2[l + 1][r];
                int p2 = piles[r] + dp2[l][r - 1];
                dp1[l][r] = math.max(p1,p2);
                int p3 = dp1[l + 1][r];
                int p4 = dp1[l][r - 1];
                dp2[l][r] = math.min(p3,p4);
                l++;
                r++;
            }
        }
        return dp1[0][n - 1] > dp2[0][n - 1];
    }