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

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

热度指数：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

输出

备注:

时间复杂度,空间复杂度

算法知识视频讲解

吃一堑长一堑

发表于 2022-03-17 12:36:05

暴力递归：对于一个玩家，有两种选择：先手或者后手；分先手函数和后手函数； import java.util.*; import java.lang.*; public class Main{ public static void main(String[] args){ 展开全文

人定胜天~

发表于 2022-02-28 09:19:21

算法思想：用暴力递归的方法： f(i,j)：表示如果arr[i…j]这个排列上的纸牌被绝顶聪明的人先拿，最终能够获得什么分数。 s(i,j)：表示如果arr[i…j] 这个排列上的纸牌被绝顶聪明的人后拿，最终能获得什么分数。在先拿的f(i,j)中： 1.如果i == j(只有一张纸牌)，会被展开全文