暴力递归——范围上尝试的模型,博弈论

简介: 暴力递归——范围上尝试的模型,博弈论

范围上尝试的模型

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

博弈论:双方玩家都不会在对方单独改变策略的情况下让对方获得最大收益

其它类似的零和博弈问题:鳄鱼吃人、海盗分金币、欧拉信封等等

package com.harrison.class12;
public class Code07_CardsInLine {
  public static int f(int[] arr,int L,int R) {
    // 如果只剩下一张牌了,又是先手,那就直接拿走最后一张
    if(L==R) {
      return arr[L];
    }
    // 如果先手拿的是左边的牌,那么后手只能在[L+1,R]上拿牌
    // 如果先手拿的是右边的牌,那么后手只能在[L,R-1]上拿牌
    // 这两种情况下,先手肯定会只选择对自己最有利的方式,也就是返回最大值
    return Math.max(arr[L]+s(arr, L+1, R), arr[R]+s(arr, L, R-1));
  }
  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));
  }
  public static void main(String[] args) {
    int[] arr= {4,7,9,5};
    System.out.println(f(arr, 0, 3));
    System.out.println(s(arr, 0, 3));
  }
}
相关文章
|
7月前
|
存储 JavaScript 前端开发
递归的递归之书:第十章到第十四章
递归的递归之书:第十章到第十四章
55 0
|
4月前
|
算法 Java 测试技术
算法分析(蛮力法与减治算法应用实验报告)
这篇文章是关于算法分析的实验报告,介绍了如何使用蛮力法解决背包问题,并通过伪代码和Java代码实现,同时分析了其时间效率;还介绍了基于减治法思想实现的二叉查找树的插入与查找,同样提供了伪代码、Java源代码实现和时间效率分析,最后展示了测试结果截图。
算法分析(蛮力法与减治算法应用实验报告)
|
6月前
|
存储 缓存 算法
动归和递归算法讲解
动归和递归算法讲解
|
7月前
|
算法 NoSQL 容器
1.贪心理论与常见的证明方法
1.贪心理论与常见的证明方法
|
7月前
|
算法 数据安全/隐私保护 决策智能
【算法训练-回溯算法 零】回溯算法解题框架
【算法训练-回溯算法 零】回溯算法解题框架
71 0
|
机器学习/深度学习 存储 算法
经典算法之——递归
经典算法之——递归
95 0
|
搜索推荐 容器
暴力递归:动态规划的雏形
暴力递归:动态规划的雏形
|
存储 算法 C++
【数独 2】候选数法解数独谜题-挖掘更深的信息-C++实现
【数独 2】候选数法解数独谜题-挖掘更深的信息-C++实现
164 1
【数独 2】候选数法解数独谜题-挖掘更深的信息-C++实现
|
算法 C++
【基础算法训练】——双指针
【基础算法训练】——双指针
129 0
【基础算法训练】——双指针
|
算法 C++ 索引
【基础算法训练】——贪心
【基础算法训练】——贪心
148 0
【基础算法训练】——贪心