首页 > 试题广场 > 纸牌博弈
[编程题]纸牌博弈
  • 热度指数:4241 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

有一个整型数组A,代表数值不同的纸牌排成一条线。玩家a和玩家b依次拿走每张纸牌,规定玩家a先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家a和玩家b都绝顶聪明,他们总会采用最优策略。请返回最后获胜者的分数。

给定纸牌序列A及序列的大小n,请返回最后分数较高者得分数(相同则返回任意一个分数)。保证A中的元素均小于等于1000。且A的大小小于等于300。

测试样例:
[1,2,100,4],4
返回:101
import java.util.*;
/*这是一道很明显的动态规划题
用F[l][r]表示先选的人能拿到的最高分
用S[l][r]来表示后选的人能拿到的最高分
如对于一组从0,1,2,...,n-1的数
对于先选者,他有两种选法
若先选者选A[0],则对于后面的1,...,n-1数组,他就变成了后选者,此时能拿到的分为A[0]+S[1][n-1]
若先选者选A[n-1],则对于前面的数组0,...,n-2,同样变为后选者,此时能拿到得分为A[n-1]+S[0][n-2];
所以 F[0][n-1]=max(A[0]+S[1][n-1],A[n-1]+S[0][n-2])
对于后选者,他能能到的最高分是受先选者控制的,即他只能选到先选者留给他的最小值,将其转化为数学形式就是
S[l][r]=min(F[l+1][r],F[l][r-1]);
这里的最小值是先选者留给他的,他只能拿到最小值,打个比方,我是先选者,我若选A[0],剩下的留给你选,这个时候主动权在你
所以你能得到的最大分必为F[1][n-1],我若选A[n-1],剩下的留给你选,这个时候主动权在你
所以你能得到的分必为F[0][n-2],我肯定是要把能得到的分少的那个留给你,所以你只能得到Min(F[1][n-1],F[0][n-2]);
*/
public class Cards {
    public int cardGame(int[] A, int n) {
        int[][]F=new int [n][n];
        int [][]S=new int [n][n];
        for(int r=0;r<n;r++){
            F[r][r]=A[r];
            S[r][r]=0;
            for(int l=r-1;l>=0;l--){
                F[l][r]=Math.max(A[l]+S[l+1][r],A[r]+S[l][r-1]);
                S[l][r]=Math.min(F[l+1][r],F[l][r-1]);
            }
        }
        return Math.max(F[0][n-1],S[0][n-1]);
    }
}

发表于 2018-04-16 18:15:08 回复(0)
	public static int cardGame(int[] A, int n) {
		int[][] f = new int[n][n];
		int[][] s = new int[n][n];
		for (int i = 0; i < n; ++i) {
			f[i][i] = A[i];
		}
		f[A.length - 2][A.length - 1] = Math.max(A[A.length - 2], A[A.length - 1]);
		for (int i = f.length - 2; i >= 0; i--)
			for (int j = i + 1; j <= f.length - 1; ++j) {
				s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
				f[i][j] = Math.max(A[i] + s[i + 1][j], A[j] + s[i][j - 1]);
			}
		return Math.max(f[0][n - 1], s[0][n - 1]);
	}
      //递归版本简单,但会超时
	public static int cardGame(int[] A, int n) {
		int scorA = F(A, 0, n - 1);
		int scorB = S(A, 0, n - 1);
		return Math.max(scorA, scorB);
	}

	public static int F(int[] arr, int l, int r) {
		if (l == r)
			return arr[l];
		return Math.max(S(arr, l + 1, r) + arr[l], S(arr, l, r - 1) + arr[r]);
	}

	public static int S(int[] arr, int l, int r) {
		if (l == r)
			return 0;
		return Math.min(F(arr, l + 1, r), F(arr, l, r - 1));
	}

a和b都是绝顶聪明,他们每次拿元素时,肯定是按对自己最有力的方式拿。该题目先由最普通的递归解法,然后进行优化,到动态规划。

递归方式,对数组arr,元素数为n。

F(arr, l , r)表示对于数组arr,元素从l到r,先拿可以达到的最大分数;

S(arr, l, r)表示对于数组arr, 元素从l到r,后拿可以达到的最大分数。

对于F(arr, l, r),先拿时,有两种拿法,拿第一个arr[l],或最后一个arr[r];如果拿arr[l],那么剩余的arr[l+1,....r]能拿到的最大分数为S(arr, l+1, r),分数为arr[l] +S(arr, l+1, r); 如果拿arr[r],剩余的arr[l, ...r-1]能拿到的最大分数为S(arr, l, r-1),分数为arr[r] + S(arr, l, r-1),因为对于先拿后剩余的数组,当前人再拿的话是后拿的,然后取这两种拿法较大的分数。

对于S(arr, l, r),如果前一个人先拿了arr[l],则后拿的分数为F(arr, l+1, r),如果前一个人先拿了arr[r],则后拿的分数为F(arr, l, r-1),因为对于剩余的元素来说,你是先拿的,取两种方式的较小值才是S的值。(为什么取较小值,而不是较大值?因为a和b都是绝顶聪明人,你是在另一个绝顶聪明人之后才拿的,他给你剩下的肯定是较坏的情况
函数关系为 F(arr, l , r) = max { S(arr,l+1,r)+ arr[l] , S(arr,l,r+1)+arr[r] }
S(arr, l, r ) = min{F(arr,l+1,r),F(arr,l,r+1)}
初始值F(arr, i, i)  = arr[i]
S(arr,i,i) = 0;
动态规划,更新过程如下图所示


编辑于 2017-06-27 23:55:44 回复(1)
import java.util.Scanner;

public class Cards {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] A = new int[n];
			for (int i = 0; i < n; i++) {
				A[i] = scanner.nextInt();
			}
			System.out.println(cardGame(A, n));
		}
	}

	public static int cardGame(int[] A, int n) {
		// f[i][j]表示在牌[i...j]下,先选能获得的最大分数
		// s[i][j]表示在牌[i...j]下,后选能获得的最大分数
		int[][] f = new int[n][n];
		int[][] s = new int[n][n];
		for (int j = 0; j < n; j++) {
			f[j][j] = A[j];
			for (int i = j - 1; i >= 0; i--) {
				// 有两种拿法:1.先手拿最左边的。那么下一次拿的时候只能后选 2.先手拿最右边的。那么下一次拿的时候只能先选
				f[i][j] = Math.max(A[i] + s[i + 1][j], A[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]);
	}
}


编辑于 2016-10-08 17:17:54 回复(2)
import java.util.*;

public class Cards {
    public int cardGame(int[] arr, int n) {
        //f[i][j]表示我先选的情况下[i...j]能获得的分数
        //s[i][j]表示我后选的情况下[i...j]能获得的分数
        int[][] f=new int[n][n];
        int[][] s=new int[n][n];
        for (int j = 0; j < n; j++) {
            //先选得到的分数f[i][i]即为arr[i],此处隐藏了s[i][i]=0,由于默认值就是零,所以可以省略
			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]);
    }
}

发表于 2016-04-23 00:18:58 回复(3)
贴一个非递归版
class Cards {
public:
    int cardGame(vector<int> A, int n) {
        // write code here
        vector<vector<int> > first(n+1,vector<int>(n,0));
        vector<vector<int> > second(n+1,vector<int>(n,0));
        first[0][0]=A[0];
        first[n-1][n-1]=A[n-1];
         
        for(int j=1;j<n;++j)
            for(int i=j;i>=0;--i){
                first[i][j]=max(A[i]+second[i+1][j],A[j]+second[i][j-1]);
                second[i][j]=min(first[i+1][j],first[i][j-1]);
        }
        return max(first[0][n-1],second[0][n-1]);
    }
};

发表于 2016-01-07 14:53:28 回复(0)
class Cards /// 记忆化搜索
{
public:
    const static int N = 303;
    int sum[N];
    int dp[N][N];
    int dfs(int l, int r, vector<int> A)
    {
        if (~dp[l][r]) return dp[l][r];
        if (l==r) return A[l];
        int ans = sum[r] - (l==0 ? 0 : sum[l-1]);
        ans -= min(dfs(l+1, r, A), dfs(l,r-1,A));
        return dp[l][r] = ans;
    }
    int cardGame(vector<int> A, int n)
    {
        sum[0] = A[0];
        for (int i=1;i<n-1;i++) sum[i]=sum[i-1] + A[i];
        memset(dp, -1, sizeof dp);
        return dfs(0, n-1, A);
    }
};
/**
考虑记忆化搜索,dp[l][r]表示l..r区间内取纸牌,先手的最大收益。
每个人要让自己收益最大,也就是让对手收益最小。
收益是l..r区间内所有纸牌的和 - 我取了之后剩下区间对手的收益。
*/
编辑于 2015-08-10 15:16:46 回复(1)
class Cards {
public:
    int cardGame(vector<int> A, int n) {
        vector<vector<int>> a(n+1,vector<int>(n,0));
        vector<vector<int>> b(n+1,vector<int>(n,0));
        a[0][0] = A[0];
        a[n-1][n-1] = A[n-1];
        
        for(int j=1;j<n;j++)
            for(int i=j;i>=0;i--)
            {
                a[i][j] = max(A[i]+b[i+1][j], A[j]+b[i][j-1]);
                b[i][j] = min(a[i+1][j], a[i][j-1]);             }                  return max(a[0][n-1], b[0][n-1]);
    }
};

发表于 2017-11-16 00:59:01 回复(0)
class Cards {
public:
    int cardGame(vector<int> A, int n) {
        //dpFirst[i][j]表示从j开始长度i的纸牌序列里#先选#得分最高的
        //dpAfter[i][j]表示从j开始长度i的纸牌序列里#后选#得分最高的,
        vector<vector<int>> dpFirst(n,vector<int>(n)),dpAfter(n,vector<int>(n));
        for(int i=0;i<n;++i){
            dpFirst[0][i]=A[i];//只有一张牌的时候先选的人得此牌分数
            dpAfter[0][i]=0;//后选的人0分
        }
        for(int i=1;i<n;++i)
            for(int j=0;j<n-i;++j){
                int k=j+i;//k为序列终点
                //先选的人,若先选左边,则剩下的序列里他是后选者,先选右边同理
                dpFirst[i][j]=max(dpAfter[i-1][j]+A[k],dpAfter[i-1][j+1]+A[j]);
                //后选的人只能在先选者选了后,剩下的里面选最小的(因为先选者肯定采用最优策略)
                dpAfter[i][j]=min(dpFirst[i-1][j],dpFirst[i-1][j+1]);
                
            }
        return max(dpFirst[n-1][0],dpAfter[n-1][0]);
    }
};

发表于 2019-03-17 19:40:43 回复(0)
循环的顺序为什么对结果有影响
i在外层,j在内层 j>i ,j++     答案不对
j在外层,i在内层 i<j,i-- 答案正确
发表于 2018-11-30 11:52:03 回复(0)
# -*- coding:utf-8 -*-
#用first[j][i]表示先选的人能拿到的最高分,second[j][i]来表示后选的人能拿到的最高分
#对于先选者,他有两种选法
#1.若先选者选A[0],则对于后面的1,...,n-1数组,他就变成了后选者,此时能拿到的分为A[0]+S[1][n-1]
#2.若先选者选A[n-1],则对于前面的数组0,...,n-2,同样变为后选者,此时能拿到得分为A[n-1]+S[0][n-2];
#所以 F[0][n-1]=max(A[0]+S[1][n-1],A[n-1]+S[0][n-2])
#对于后选者,他能能到的最高分是受先选者控制的,即他只能选到先选者留给他的最小值,将其转化为数学形式就是
#S[l][r]=min(F[l+1][r],F[l][r-1])
#这里的最小值是先选者留给他的,他只能拿到最小值
class Cards:
    def cardGame(self, A, n):
        first=[[0 for i in range(n)] for i in range(n)]
        second=[[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            first[i][i]=A[i]
            second[i][i]=0
            j=i-1
            while j>=0:
                first[j][i]=max(second[j+1][i]+A[j],second[j][i-1]+A[i])
                second[j][i]=min(first[j+1][i],first[j][i-1])
                j-=1
        return max(first[0][n-1],second[0][n-1])

发表于 2018-10-04 19:48:24 回复(0)
class Cards {
public:
    
    int cardGame(vector<int> A, int n) {
        // write code here
        Index = vector<vector<pair<int,int>>>(n, vector<pair<int,int>>(n,make_pair(-1,-1)));
        auto result = maxMoney(A, 0, n-1);
        
        return max(result.first, result.second);
    }
    
private:
    //表示在[first,end]中选择可以获得最大的收益,返回一个pair,第一个数表示当前选择可以获得最大的值,第二个数表示上一个选择可以获得最大的数
    vector<vector<pair<int,int>>> Index;
    pair<int,int> maxMoney(const vector<int>& A, int firstIndex, int endIndex)
    {
        if((endIndex - firstIndex) == 1){
            int other = min(A[firstIndex], A[endIndex]);
            int now = max(A[firstIndex], A[endIndex]);
            return make_pair(now, other);
        }
        if(Index[firstIndex][endIndex].first != -1)
            return Index[firstIndex][endIndex];
        
        auto choseLeft = maxMoney(A, firstIndex+1, endIndex);
        
        auto choseRight = maxMoney(A, firstIndex, endIndex-1);
        
        if((A[firstIndex] + choseLeft.second) > (A[endIndex]+choseRight.second)){
            Index[firstIndex][endIndex] = make_pair(A[firstIndex] + choseLeft.second,choseLeft.first);
            return Index[firstIndex][endIndex];
        }
        else{
            Index[firstIndex][endIndex] = make_pair(A[endIndex]+choseRight.second,choseRight.first);
            return Index[firstIndex][endIndex];
        }
    }
};
发表于 2018-08-01 17:17:27 回复(0)
import java.util.*;

public class Cards {
    public int cardGame(int[] A, int n) {
        // write code here
        int[][] f=new int[n][n];
        int[][] s=new int[n][n];
        for(int i=0; i<n; i++){
            f[i][i]=A[i];
            for(int j=i-1; j>=0; j--){
                f[j][i]=Math.max(A[j]+s[j+1][i], A[i]+s[j][i-1]);
                s[j][i]=Math.min(f[j+1][i], f[j][i-1]);
            }
        }
        return Math.max(f[0][n-1], s[0][n-1]);
    }
}

发表于 2018-06-27 16:22:27 回复(0)
def maxs(low,high,data):     if low == high-1:         return max(data[low],data[high])     else:         return max(data[low]+mins(low+1,high,data),data[high]+mins(low,high-1,data)) def mins(low,high,data):     if low == high-1:         return min(data[low],data[high])     else:         return min(maxs(low+1,high,data),maxs(low,high-1,data)) def main():     data = [1,5,3,4,7,2,6,3]     print(maxs(0,len(data)-1,data))

if __name__=="__main__":     main()  #来个python

发表于 2018-06-02 20:45:19 回复(0)
public class Cards {
    public int cardGame(int[] A, int n) {
            //f-即你拥有主动权的时候
            int[][] f = new int[n][n];
            //s-侧重体现是对面会留给你什么样的结果
            int[][] s = new int[n][n];
            for (int j = 0; j < n; j++) {
                f[j][j] = A[j];
                for (int i = j - 1; i >= 0; i--) {
                    f[i][j] = Math.max(A[i] + s[i + 1][j], A[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]);
    }
}

发表于 2018-01-06 19:38:16 回复(0)
 
/*
    分析:
动态规划dpFirst[i][j](i<=j)代表A[i~j]内最先取的人的最高分数,dpSecond[i][j](i<=j)代表A[i~j]内后取的人的最高分数

分析特殊情况:
dpFirst[j][j] = A[j];//即只有一个元素的情况下,最先取的人的得分即A[j]
dpSecond[j][j] = 0;//即只有一个元素的情况下,后取的人的得分为0
一般情况:
dpFirst[i][j]有两种情况:(双方都很聪明,所以第一次指定取到最大的)
1)先取头部元素A[i],则后面第二次取dpSecond[i+1][j]
2)先取尾部元素A[j], 则后面第二次取dpSecond[i][j-1]

dpSecond[i][j]有两种情况(双方都很聪明,所以第二次取只能取到最小的)
1)先手已经取了首部元素,则后手下次应该第一次取dpFirst[i+1][j]
2)先手已经取了尾部元素,则后手下次应该第一次取dpFirst[i][j-1]

*/
    int cardGame(vector<int> A, int n)
    {
        vector<vector<int>> dpFirst(n, vector<int>(n));
        vector<vector<int>> dpSecond(n, vector<int>(n));

        for (int j = 0; j < n; j++)
        {
            dpFirst[j][j] = A[j];
            dpSecond[j][j] = 0;
            for (int i = j - 1; i >= 0; i--)
            {
                dpFirst[i][j] = max(A[i] + dpSecond[i+1][j], A[j] + dpSecond[i][j-1]);
                dpSecond[i][j] = min(dpFirst[i+1][j], dpFirst[i][j-1]);
            }
        }
        return max(dpFirst[0][n-1], dpSecond[0][n-1]);
    }
发表于 2017-09-04 13:04:45 回复(0)
	public static int cardGame(int[] A, int n) {
		// f[i][j]表示:在卡片是[i...j]时,此刻的后选者能获得的分数
		// s[i][j]表示:在卡片是[i...j]时,此刻的先选者能获得的分数
		// 如,f[3][6]表示剩余待取卡片范围是3到6时,此刻的先选者能获得的分数
		int[][] f = new int[n][n];
		int[][] s = new int[n][n];
		for (int j = 0; j < n; j++) {
		    // 当有 j+1 张卡片的时候,可以计算出:
			// 剩下只有第 j 张卡片时的情况,
			// 剩下第 j-1 到第 j 张卡片时的情况,
			// 剩下第 j-2 到第 j 张卡片时的情况,
			// ......
			// 剩下第 0 到第 j 张卡片时的情况。		
			// s[j][j] = 0; // 只有一张卡片时,后选者s[j][j] = 0;
			f[j][j] = A[j]; // 只有一张卡片时,先选者直接赋值即可。
			for (int i = j - 1; i >= 0 ; i--) {
				// 计算第 i 到第 j 张卡片时的情况,i = {j-1, j-2, ..., 0}
				// 计算先选者:
				// 本次选择完成后,在下次选择中变为后选者。
				// 分别判断选择最左和最右时的情况,使本次选择最优。
				// 选择最左第 i 张时,那下次就是第 i+1 到第 j 张卡片的后选者。
				// 选择最右第 j 张时,那下次就是第 i 到第 j+1 张卡片的后选者。
				// 比较两种选择方式,找到最优的结果。
				f[i][j] = Math.max(A[i] + s[i+1][j], A[j] + s[i][j-1]);
				// 计算后选者:
				// 本次先选者选完后,由本次的后选者选下一张牌,后选者是下一次的先选者。
				// 后选者本次不是实际进行拿牌,实际拿牌是下次以先选者的身份,所以计算后选者不用加上A[i]或A[j]。
				// 双方都很聪明,使后选者只能获取较小的分数。
				// 即,因为本次先选者的选择,使得后选者只能选择结果较小的分数
				s[i][j] = Math.min(f[i+1][j], f[i][j-1]);
			}
		}
		
		return Math.max(f[0][n-1], s[0][n-1]);
	}
编辑于 2017-08-14 19:44:23 回复(0)
昨晚听了左神将这题 今天试一下   import java.util.*;

public class Cards {
    

		/**
	 * @param arr
	 * @return
	 */
	public int cardGame(int[] arr, int n){
		
		if (arr == null || arr.length == 0) {
			return 0;
		}
		
		int sum = 0;
		for (int i : arr) {
			sum += i;
		}
		int firstVaule = first2(arr);
		return Math.max(firstVaule, sum - firstVaule);
	}
	
	public  int first2(int[] arr){
		int n = arr.length;
		int[][] first = new int[n][n];
		boolean odd = n % 2 == 1 ?  true: false;	//数组是否是奇数数组
		
		for (int i = 0; i < first.length; i++) {
			if (odd) {
				first[i][i] = arr[i];
			}
			
			for (int j = i - 1; j >= 0; j--) {
				if (odd ? (i +j) % 2 == 1 : (i +j) % 2 != 1 ) {
					first[i][j] = Math.min(first[i - 1][j], first[i][j + 1]);
				}else{
					first[i][j] = Math.max(arr[i] + first[i - 1][j], arr[j] + first[i][j + 1]);
				}
			}
		}
		
		return first[n - 1][0];
	}
	
}
发表于 2017-07-20 16:59:31 回复(0)
测试用例:
[38,12,58,91,54,73,11,15,89,93,77,21,20,12,58,47,41,58,37,93,23,74,6,60,41,9,0,64,15,32,45,24,64,42,90,66,7,38,79,70,92,37,58,11,75,97,77,50,53,82,59,34,9,34,14],55

对应输出应该为:

1354

你的输出为:

1377
发表于 2017-07-12 15:17:42 回复(0)
分享一个python代码
 # -*- coding:utf-8 -*-
class Cards:
    def cardGame(self, A, n):
        first = []
        second = []
        for i in range(n):
            first.append([0 for i in range(n)])
            second.append([0 for i in range(n)]) 
        first[0][0] = A[0]
        first[n-1][n-1]=A[n-1]
        for j in range(1,n):
            for i in range(n-2,-1,-1):
                if i<=j:
                    first[i][j] = max(second[i+1][j]+A[i],second[i][j-1]+A[j])
                    second[i][j] = min(first[i+1][j],first[i][j-1])
        return int(max(first[0][n-1],second[0][n-1]))

发表于 2017-07-10 22:59:20 回复(0)
/*经典DP了

最优子结构:
n张牌0,1,...,n-1;第一步
A作为先手要么拿第0张,要么拿第n-1张(原因是题目里说
只能从两端拿牌),拿了之后在剩下n-1张牌里A作为后手,
能获得最大得分, 也就是B作为先手在n-1张牌里得到大得分
后剩下多少分。 dp[i][j] = A[i]   //i==j  dp[i][j] = std::max(
            sum(A[i]...A[j]) - dp[i+1][j], //拿左边
            sum(A[i]...A[j]) - dp[i][j-1]) //拿右边 
         = sum(A[i]...A[j]) - std::min(dp[i+1][j], dp[i][j-1]
         = sum[j] - sum[i] + A[i] - std::min(dp[i+1][j], dp[i][j-1])
         (i<j)
为了方便计算,可以先计算好sum[i] = sum(A[0]...A[i]) 重叠子问题:
计算dp[i+1][j]与dp[i][j-1]都依赖子问题dp[i+1][j-1],所以有重叠
子问题。

综上:动态规划可解。    
*/
class Cards {
public:
    int cardGame(vector<int> A, int n) {
        // write code here
        int i;
        for(i = 0; i < n; i++){
            dp[i][i] = A[i];
            if(i == 0) 
                sum[0] = A[i];
            else
                sum[i] = sum[i-1] + A[i];
        }
        
        for(int step = 2; step <= n; step++){
            for(i = 0; i <=n && i+step<=n; i++){
                int j = i+step-1;
                dp[i][j] = sum[j] - sum[i] + A[i] -
                           std::min(dp[i+1][j], dp[i][j-1]);
            }
            
        }
        return std::max(dp[0][n-1], sum[n-1] - dp[0][n-1]);
    }
    int dp[301][301];
    int sum[301];
};

编辑于 2017-05-21 19:51:20 回复(0)

问题信息

难度:
26条回答 12325浏览

热门推荐

通过挑战的用户

查看代码