排成一条线的纸牌博弈问题

[编程题]排成一条线的纸牌博弈问题

热度指数：5107 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

4
1 2 100 4

输出

备注:

时间复杂度,空间复杂度

算法知识视频讲解

Java

pein531

这道题仍然可以用暴力递归尝试改动态规划的套路，先给出暴力的递归尝试（会超时）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strCards = br.readLine().split(" ");
        int[] cards = new int[n];
        for(int i = 0; i < n; i++) cards[i] = Integer.parseInt(strCards[i]);
        System.out.println(first(cards, 0, cards.length - 1));     // 假设A玩家先，并让他获胜
    }
    
    // 先手函数
    private static int first(int[] cards, int left, int right) {
        if(left == right) return cards[left];      // 剩最后一张牌，拿走
        // 先手利益最大化
        return Math.max(cards[left] + second(cards, left + 1, right), cards[right] + second(cards, left, right - 1));
    }
    
    // 后手函数
    private static int second(int[] cards, int left, int right) {
        if(left == right) return 0;      // 剩最后一张牌，被先手的拿了
        return Math.min(first(cards, left + 1, right), first(cards, left, right - 1));    // 先手留最少的给后手
    }
}

然后根据递归的依赖关系改出动规版本：(1)有两个递归函数，就有两张动态规划表；(2)对于区间[left,right]上面的结果，dp[left][right]依赖left+1和right-1，因此left从大往小遍历，right从小往大遍历；(3)left不能大于right，因此动态规划表中left>right的区域无效。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strCards = br.readLine().split(" ");
        int[] cards = new int[n];
        for(int i = 0; i < n; i++) cards[i] = Integer.parseInt(strCards[i]);
        // 先手和后手一起动规
        int[][] dpFirst = new int[n][n];
        int[][] dpSecond = new int[n][n];
        for(int right = 0; right < n; right ++){
            for(int left = right; left >= 0; left --){
                if(left == right){
                    // 只剩一张牌，先手的拿
                    dpFirst[left][right] = cards[left];
                    dpSecond[left][right] = 0;
                }else if(left < right){
                    dpFirst[left][right] = Math.max(cards[left] + dpSecond[left + 1][right], cards[right] + dpSecond[left][right - 1]);
                    dpSecond[left][right] = Math.min(dpFirst[left + 1][right], dpFirst[left][right - 1]);
                }
            }
        }
        System.out.println(Math.max(dpFirst[0][n - 1], dpSecond[0][n - 1]));
    }
}

编辑于 2021-11-20 17:16:12 回复(0)

Java

叫我小du

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[][] dpf = new int[n][n];
        int[][] dps = new int[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = n - 1; i >= 0; i--) {
                if (i > j) {
                    continue;
                } else if (i == j) {
                    dpf[i][j] = arr[i];
                    dps[i][j] = 0;
                } else {
                    dpf[i][j] = Math.max(arr[i] + dps[i + 1][j], arr[j] + dps[i][j - 1]);
                    dps[i][j] = Math.min(dpf[i + 1][j], dpf[i][j - 1]);
                }
            }
        }
        int res = Math.max(dpf[0][n - 1], dps[0][n - 1]);
        System.out.println(res);
    }
}

发表于 2021-04-09 14:05:29 回复(0)

Java

眼睛想旅行121

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.print(win(n,arr));
    }
    public static int win(int n,int[] arr){
        if(arr==null||n==0){
            return 0;
        }
        int[][] f=new int[n][n];
        int[][] s=new int[n][n];
        for(int j=0;j<n;j++){
            f[j][j]=arr[j];
            for(int i=j-1;i>=0;i--){
                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]);
            }
        }
        return Math.max(f[0][n-1],s[0][n-1]);
    }
}

发表于 2021-03-29 14:41:28 回复(0)

Java

jahentao

动态规划。

假设函数f(i,j)表示绝顶聪明的玩家，先拿[i,j]区间内的纸牌，获得的最大分数；s(i,j)表示绝顶聪明的玩家，后拿[i,j]区间内的纸牌，获得的最大分数。

时间复杂度O(N²)，空间复杂度O(N²)不超过限制，可以压缩为O(N)。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = a[i];
            s[i][i] = 0;
        }
        for (int d = 1; d < n; d++) {
            for (int i = 0; i < n - d; i++) {
                f[i][i + d] = Math.max(a[i] + s[i + 1][i + d], a[i + d] + s[i][i + d - 1]);
                s[i][i + d] = Math.min(f[i + 1][i + d], f[i][i + d -1]);
            }
        }
        System.out.println(Math.max(f[0][n-1], s[0][n-1]));
    }
}

发表于 2020-05-08 07:40:27 回复(0)