【dfs && 记忆化搜索&&区间dp】排成一条线的纸牌博弈问题

描述

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

输入描述：

输出包括两行，第一行一个整数n(1≤n≤5000)(1≤n≤5000)，代表数组arr长度，第二行包含n个整数，第i个代表arr[i](1≤arr[i]≤105)(1≤arr[i]≤105)。

输出描述：

输出一个整数，代表最后获胜者的分数。

示例1

输入：

4
1 2 100 4

输出：

101

备注：

时间复杂度O(n2)O(n2),空间复杂度O(n2)O(n2)

此题同 【dfs && 记忆化搜索&&区间dp】leet-486. 预测赢家类似，上一题要求是否能赢也就是最大差值>=0, 本题要求获胜者的分数.

从上一题得知道 先手的相对分数 diff=score1-score2=dp[0][n-1] , 而题目得知：score1+score2=数组之和sum.

所以：score1 = (sum+diff)/2, score2=sum-score1; 获胜者分数=Math.max(score1, score2)

代码：

   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] cards = new int[n];
            for (int i = 0; i < n; i++) cards[i] = in.nextInt();

            int sum = Arrays.stream(cards).sum();
            int diff = predictTheWinner(cards);
            int score1 = (sum + diff) / 2;
            int score2 = sum - score1;
            System.out.println( Math.max(score1, score2));
        }
    }

    public static int predictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int r = 1; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r) dp[l][r] = nums[l];
                else dp[l][r] = Math.max(nums[l] - dp[l + 1][r], nums[r] - dp[l][r - 1]);
            }
        }
        return dp[0][n - 1];
    }

相似题目：【dfs && 记忆化搜索&&区间dp】leet-486. 预测赢家