纸牌博弈

[编程题]纸牌博弈

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

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

测试样例：

[1,2,100,4],4

返回：101

算法知识视频讲解

重生之我要当分子

发表于 2025-01-01 01:30:13

解题思路这是一个博弈论问题，使用动态规划求解。关键点：状态定义： a[i][j] 表示在区间 [i, j] 内先手能获得的最大分数 b[i][j] 表示在区间 [i, j] 内后手能获得的最大分数状态转移：先手可以选择最左或最右的牌：选左边：A[i] + b[i+1][j] 展开全文

问题信息

动态规划

来自：面试常考算法题(十)-...

难度：

26条回答 122收藏 15226浏览

查看代码

纸牌博弈

扫一扫，把题目装进口袋